1 Introduction

The success of deep learning models has typically been measured in terms of their predictive power, but they have lacked a principled way of expressing uncertainty about these predictions.

In my master’s thesis we apply recent insights connecting dropout neural networks to Bayesian approximate variational inference (VI). VI is technique for approximating intractable integrals that arise when modelling the posterior distribution in Bayesian inference and machine learning. Gal et. al. [1, 2, 3] have shown that the posterior distribution of a NN can be approximated by leaving dropout on at test time and sampling multiple predictions. This amounts to drawing Monte Carlo (MC) samples from the posterior distribution (a brief description of this process is listed in section 1.1). The Bayesian framework allows us to obtain principled uncertainty estimates when making predictions in these so called MC dropout NNs.

The results of [1,2,3] seem particularly promising when applied to healthcare. In fact, a recent paper published in Nature [4] applies MC dropout to capture uncertainty estimates when predicting the presence of diabetic retinopathy in patients. This paper demonstrates how uncertainty estimates can provide useful information to the clinician tasked with interpreting the results of medical images. The key idea is that this human-machine interaction will lead to overall better results than either could produce individually.

In this notebook I will first briefly introduce the general idea behind MC dropout. Then we will demonstrate how MC dropout has been applied in existing literature through a practical example. We will use the fastai framework, and the goal is to estimate uncertainty on a classification task based on the collection of labelled images in the CIFAR-10 data set.

1.1 Background

A neural network is made up of many neurons which are organized in layers. Neurons are often called nodes or units, depending on your choice of machine learning literature. Henceforth we will refer to them as units.

In a typical neural network there are many, many units. As a consequence the number of parameters greatly exceeds the number of data points, dramatically increasing the risk of overfitting (i.e. there are many settings of weights which will cause the network to fit the data almost perfectly).

Dropout is a common stochastic regularisation technique [5] that is used to prevent overfitting in neural networks. The term dropout refers to randomly “dropping out” nonoutput units, temporarily removing all connections to the rest of the network. The main idea is that if the presence of other units is unreliable, each unit is forced to learn how to be useful on its own. At test time all units are activated, and the weights of the network are scaled by the dropout rate in order to match the expected output during training.

Recent work by Gal et. al. [1, 2, 3] casts dropout neural networks as approximate Bayesian inference. Their results show that the predictive posterior distribution of a neural network can be approximated by leaving dropout on at test time.

Consider a classification setting, such as in CIFAR-10. Essentially, what happens when applying MC dropout is the following:

  • An image is fed forward through the network \(T\) times (we use \(T=100\) as recommended in [4]). Each time the image is fed through is called a stochastic forward pass.
  • For each stochastic forward pass, a slightly different network is making predictions because dropout has randomly switched off units.
  • As a result each stochastic forward pass returns 100 slightly different vectors of class predictions.
  • To make a prediction we average the 100 vectors. The is called the predictive mean vector, denoted by \(\hat{\mu}\). The class corresponding to the largest element in the resulting vector is our final prediction, i.e. \(p(y=k|X,w) = \text{argmax}_k \hat{\mu}\).
  • Finally we calculate the standard deviation in class predictions over all forward passes. This is our estimated uncertainty.

Gal et. al. [3] show that the above amounts to drawing Monte Carlo samples from the predictive posterior. Their work demonstrates that applying dropout is effectively the same as defining a Bayesian neural network with a Bernoulli approximating prior over the parameters. Gal has written an excellent blog post that introduces the work and the derivation.

In practical applications [4], model uncertainy is approximated by the empirical standard deviation of the predictions for class \(k\), i.e. \[\hat{\sigma}_k = \sqrt{\frac{\sum_{t=1}^T{[p_t(k|X,w) - \hat{\mu}_k}]^2}{T-1}}\] where \[\hat{\mu}_k = \frac{1}{T}\sum_{t=1}^T p_t(k|X,w)\] is the averaged softmax outputs of the predicted class. This is a somewhat ad hoc approximation, but recent research suggests that \(\hat{\sigma}_k\) is a meaningful uncertainty estimate [7].

1.2 Problem statement

The derivation in Gal et. al. [2] is based on the observation that a shallow neural network with infinitely many weights converges to a Gaussian process (GP) with a specific covariance function. A GP is a non-parametric, probabilistic machine learning method. The idea is that we place a prior distribution over the function space, and by observing new data points we can figure out which function is most likely to have generated the observed data. A GP is fully specified by its mean and covariance functions, and allows us to obtain uncertainty estimates [1]. The extension of this to dropout neural networks is the main result of Gal et. al. [2].

In [1] however, Gal et. al. extend this idea further to include priors over the weights of the convolutional layers in a convolutional neural network (CNN). A CNN is a specialized type of neural network, used primarily and very effectively for image analysis. The authors briefly state that the GP interpretation is lost when the model is extended to CNNs, but that these networks still can be “modelled as Bayesian”.

As far as we are aware, there have been no efforts to determine the correlation between the approximated uncertainty and a network’s ability to predict correctly. Moreover, the work done so far seems to focus on the uncertainty associated with the predicted class. In other words, our problem statement is:

Are the uncertainty approximations obtained by applying Monte Carlo dropout to convolutional neural networks a reasonable measure of model uncertainty?

We will also examine if there is any additional information to be gained from establishing a connection between the prediction and the runner-up prediction.

2 Setup

In this notebook we use the following R packages: tidyverse and ggplot2. In addition we use the multiplot functionality provided by Cookbook for R. In Python we use fastai, numpy and pandas. Full code for training and inference available at GitHub. All code for the exploratory data analysis is included in this document.

2.1 Experimental setup

State-of-the-art architectures such as ResNet and DenseNet are very powerful, but they are also complicated and their inner workings are quite convoluted. We are primarily interested in examining the correlation between uncertainty estimation and predictive capabilities. It is arguably better to use a simple network architecture to illustrate the idea of MC dropout. In our approach we use LeNet-5. Click on the tabs for implementation details. Full code is available on GitHub. In the following we assume basic familiarity with NNs and specifically CNNs. NOTE: Click on Code-tab to expand chunks.

2.1.1 Model

LeNet-5 was a pioneering 7-layer convolutional neural network originally developed by Yann LeCunn in 1998 for handwritten digit recognition. It is hopelessly primitive compared to contemporary architectures, but is very useful for experimentation and proof-of-concept work due to it’s simplicity. The following chunk shows the model architecture:

class lenet_all(nn.Module):
    def __init__(self, conv_size=conv_size, pool_size=2, drop_rate=p):
        super().__init__()
        self.drop_rate = drop_rate
        self.conv1 = nn.Conv2d(in_channels=3, out_channels=192, kernel_size=conv_size)
        self.dropmc1 = DropoutMC(p)
        self.pool1 = nn.MaxPool2d(kernel_size=pool_size, stride=2)
        self.conv2 = nn.Conv2d(in_channels=192, out_channels=192, kernel_size=conv_size, padding=2)
        self.dropmc2 = DropoutMC(p)
        self.pool2 = nn.MaxPool2d(kernel_size=pool_size, stride=2)
        self.dense1 = nn.Linear(in_features=7*7*192, out_features=1000)
        self.dropmc3 = DropoutMC(p)
        self.dense2 = nn.Linear(in_features=1000, out_features=10)
        
    def forward(self, x):
        x = self.dropmc1(self.conv1(x))
        x = self.pool1(x)
        x = self.dropmc2(self.conv2(x))
        x = self.pool2(x)
        x = x.view(x.size(0), -1)
        x = self.dropmc3(F.relu(self.dense1(x)))       
        x = self.dense2(x)
        
        return x


2.1.2 MC dropout layer

Our specification of LeNet-5 differs from the orginial in one crucial way: We use MC dropout layers. MC dropout is not a feature that is implemented in PyTorch, and we must therefore implemenet such a layer ourselves. Fortunately, this amounts to a simple adjustment of existing code. We modify the Dropout class to take an additional argument called dropoutMC with default value set to True:

class DropoutMC(nn.Module):
    r"""
    Modified version of Dropout from torch/nn/modules/dropout.py
    Args:
        p: probability of an element to be zeroed. Default: 0.5
        dropoutMC: If set to ``True``, dropout is turned on at test time. Default: ``True`
        inplace: If set to ``True``, will do this operation in-place. Default: ``False``
    Shape:
        - Input: `Any`. Input can be of any shape
        - Output: `Same`. Output is of the same shape as input
    Examples::
        >>> m = nn.Dropout(p=0.2)
        >>> input = autograd.Variable(torch.randn(20, 16))
        >>> output = m(input)
    .. _Improving neural networks by preventing co-adaptation of feature
        detectors: https://arxiv.org/abs/1207.0580
    """

    def __init__(self, p=0.5, dropoutMC=True, inplace=False):
        super(DropoutMC, self).__init__()
        if p < 0 or p > 1:
            raise ValueError("dropout probability has to be between 0 and 1, "
                             "but got {}".format(p))
        self.p = p
        self.dropoutMC = dropoutMC
        self.inplace = inplace

    def forward(self, input):
        return F.dropout(input, self.p, self.dropoutMC, self.inplace)

    def __repr__(self):
        inplace_str = ', inplace' if self.inplace else ''
        return self.__class__.__name__ + '(' \
            + 'p=' + str(self.p) \
            + inplace_str + ')'


2.1.3 Inference

We need to define a function that performs inference over out input. The following chunk contains the relevant code for the sampling procedure described in section 1.1. The function inference stores all the relevant statistics and softmax distributions in a dictionary named output. The results are then turned into a pandas dataframe and some very basic feature engineering is performed. Finally, the data is prepared for statistical analysis in R.

def inference(learner, data, T=100):
    ''' Function that gathers all relevant numerical results from MC dropout over T iterations.
        
        Arguments:
        learner, fastai learner object
        data, fastai dataloader
        T, number of stochastic forward passes
    '''
    # Get images, labels and filenames
    imgs, labels = next(iter(data.val_dl))
    fnames = data.val_ds.fnames

    # Empty dictionary to store all output
    output = {}

    # Empty array to store results in
    results = np.empty((T, num_classes))

    # iterator index to keep in dictionary
    k=0

    for (img, label, fname) in list(zip(imgs, labels, fnames)):

        for i in range(T):
            prediction = learner.predict_array(img[None])
            results[i] = prediction

        probs = to_np(F.softmax(V(results)))
        probs_mean = np.mean(probs, axis=0)
        pred_std = np.std(probs, axis=0)

        prediction = probs_mean.argmax()
        uncertainty = pred_std[prediction]

        correct = 1 if prediction == label else 0

        output[k] = {"img": fname, "softmax_dist": probs, "probs": probs_mean, "prediction": prediction, "truth": label, "uncertainty": uncertainty, "correct": correct}
        k+=1
    
    return output

2.2 Training

Our model was trained on CIFAR-10 using the fastai API. CIFAR-10 contains 60.000 labelled 32x32x3 color images belonging to 10 different classes. The input data was split into a training set of 50.000 images and a test set of 10.000 images. The training set was further split into a training set and a validation set.

The network was trained for 60 epochs with a learning rate of \(0.001\) (found using lr_find functionality in fastai), kernel size = (5,5), drop_rate = .5 and weight_decay = 0.0005. It is identical in structure to the one used by Gal et. al. [1]. The validation loss was 0.71280 at end of training with an accuracy of 0.76137 on the validation data.

2.3 Data

The data contains the following variables after it has been prepared for analysis in R:

  • correct (logical): indicator the is TRUE if the predicted class label matches the true class label, else FALSE.

  • prediction (int): predicted class label.

  • truth (int): true class label.

  • uncertainty (dbl): empirical standard deviation of softmax values for predicted class.

  • prob1 (dbl): argmax of mean softmax output, i.e. mean probability of predicted class.

  • prob2 (dbl): mean probability of runner-up prediction.

  • class2 (int): class label of runner-up prediction.

  • diff (dbl): prob1-prob2

  • diff_sd_ratio (dbl): diff/uncertainty.

All the variables above are pretty standard, with the exception of diff_sd_ratio. Intuitively, if diff is large, the averaged models all agree that class \(k\) is the correct prediction. If diff is small, the models sampled by MC dropout don’t agree on a single class. Thus diff also serves as a proxy for uncertainty. Model uncertainty, however, is approximated by the empirical standard deviation of the predictions for class \(k\). Thus diff_sd_ratio is expressed by \[\tau_{kj} = \frac{\hat{\mu}_k - \hat{\mu}_j}{\hat{\sigma}_k}\] where \(j\) is the runner-up prediction. \(\tau_{jk}\) gives us a ratio of two different measures of uncertainty.

3 Classification Results

The following table summarises the results over the entire data set:

# Importing data
data <- read.csv("~/Documents/Masteroppgave/Data/Resultater/lenet-model55.csv")
df <- dplyr::select(data, -X)
# Aggregating summary statistics by correct/incorrect
results <- df %>%
  summarise(n=n(),
            accuracy = sum(correct==1)/n,
            mean_prob1=mean(prob1),
            mean_prob2=mean(prob2),
          mean_uncertainty=mean(uncertainty),
          median_uncertainty=median(uncertainty),
          sd_uncertainty=sd(uncertainty), 
          mean_diff=mean(diff),
          median_diff=median(diff),
          sd_diff=sd(diff),
          mean_ratio=mean(diff_sd_ratio),
          median_ratio=median(diff_sd_ratio),
          sd_ratio=sd(diff_sd_ratio))
results

The next table shows the summary statistics after partitioning the data by incorrect/correct classifications:

# Aggregating summary statistics by correct/incorrect
agg_df <- df %>% 
  group_by(correct) %>% 
  summarise(n=n(),
            accuracy=n/10000,
            mean_prob1=mean(prob1),
            mean_prob2=mean(prob2),
          mean_uncertainty=mean(uncertainty),
          median_uncertainty=median(uncertainty),
          sd_uncertainty=sd(uncertainty), 
          mean_diff=mean(diff),
          median_diff=median(diff),
          sd_diff=sd(diff),
          mean_ratio=mean(diff_sd_ratio),
          median_ratio=median(diff_sd_ratio),
          sd_ratio=sd(diff_sd_ratio))
agg_df

Overall our model classifies 7916 images correctly out of \(N=10.000\), giving it an accuracy of 79.16%. In brief, the summary statistics indicate that softmax outputs of the predicted and runner-up classes seem to be closer to each other when the model misclassifies. Furthermore, incorrectly classified images seem to be associated with greater uncertainty on average. This result is of crucial importance and is a necessary condition for exploring how uncertainty approximation correlates with model predictions.

The model is most successful when classifying images of automobiles (902 correct) and frogs (891 correct). The least successful predictions occur in the cat category, with 565 correct classifications. This is summarized in the following confusion matrix:

The confusion matrix above provides details of exactly how the model fails. In images of cats the most frequent misclassification is dog (145). For dogs the most frequent incorrect label is cat (135). In general it seems that the misclassifications, although wrong, belong to the same domain as the correct label (i.e. one vehicle type is mistaken for another and one species of animal is misclassified as another). This suggests that our model is unable to learn distinguishing features which adequately seperate similar classes. However, one should cautious about reading too much into the type of errors being made. The results may very well be an artefact of the model, the data set or both.

3.1 Examples of Uncertain Classifications

In the following we will visualize the relationships between our variables. We start by looking at examples of certain and uncertain images. The we examine the empirical distribution of the uncertainty estimates \(\hat{\sigma}_k\).

3.1.1 Incorrect classifications

The following plots were generated using Python (code available on GitHub). On the left hand side we see the unnormalized image with the corresponding ground truth label. The plot in the middle shows the softmax output of the predicted class for each of the \(T=100\) stochastic forward passes. \(\mu_k\) is given by the solid red line, \(\mu_j\) is given by the dashed brown line. The plot title shows both the predicted class and the runner-up class. To the right is a kernel density estimate (using a Gaussian kernel) of the \(T=100\) softmax outputs for the predicted class. The plots show the top 5 most uncertain classifications in the entire data set.

3.1.2 Correct classifications

The runner-up prediction for the five most uncertain but correct predictions are all “airplane”. One possible explanation is the presence of large areas of blue and/or white, which we might assume would be present as backgrounds in images of planes flying through the sky.

3.2 Distribution of Uncertainty

The distribution of total uncertainty appears to be bimodal, with peaks close to 0 and 0.2:

# Distribution of estimated uncertainty
p1 <- df %>% 
  ggplot(aes(x=uncertainty)) +
  geom_histogram(col="grey", bins = 50, alpha=.5) +
  ggtitle("Distribution of estimated uncertainty") +
  theme_bw()
p1

By grouping the uncertainty estimates by correct (i.e. if the label was correctly predicted or not), we can find out how the predictions contribute to the uncertainty distribution:

#Distribution of estimated uncertainty by prediction
p2 <- df %>% 
  ggplot(aes(x=uncertainty, col=as.factor(correct))) +
  geom_freqpoly(alpha=.7) +
  ggtitle("Distribution of estimated uncertainty by classification") +
  scale_color_discrete(name="Prediction",
                         breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  theme_bw()
p2

The blue line corresponds to the correct predictions, the red line corresponds to incorrect predictions. We see that the incorrect predictions are centered around a higher associated uncertainty, whereas far more of the correctly predicted classes are concentrated around a low uncertainty value. The incorrect classifications greatly contribute to the bimodality, but it is also present in the distribution of uncertainty for the correct classifications.

The following density plots gives us an idea of how the distributions compare to eachother:

# KDE by correct prediction
lines_df <- df %>% 
  group_by(correct) %>% 
  summarise(mean_uncertainty=mean(uncertainty))
p3 <- df %>% 
  ggplot(aes(x=uncertainty, group=factor(correct))) +
  geom_histogram(aes(y=..density.., fill=factor(correct)), position="identity", bins = 50, alpha=.5) +
  geom_density(aes(y=..density.., col=factor(correct)), alpha=.5) +
  geom_rug(aes(x=uncertainty, col=factor(correct)), alpha=.5) +
  geom_vline(data = lines_df, aes(xintercept=mean_uncertainty, col=factor(correct)), lty="dashed") +
  ggtitle("Distributions of uncertainty by classification") +
  labs(color="Prediction",
       fill="Prediction") +
  scale_color_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  scale_fill_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  theme_bw() +
  theme(legend.position = c(.9,.85))
p3

The boxplot gives us yet another way to visualize the difference between uncertainty distributions by predictive ability:

# Boxplot of uncertainties for correct vs. incorrect
p4 <- df %>% 
  ggplot(aes(x=as.factor(correct), y=uncertainty)) +
  geom_boxplot(aes(fill=as.factor(correct)), alpha=.7) +
  labs(x="correct") +
  ggtitle("Boxplot of uncertainty distribution by correct/incorrect") +
  scale_fill_discrete(name="Prediction",
                         breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) + 
  theme_bw()
p4

If \(\hat{\sigma}_k\) is a useful approximation of model uncertainty, then we would expect the distributions \(\hat{\sigma}_k\) for correctly and incorrectly classified images to reflect this somehow. From the figures above, it seems clear that the distributions of uncertainties are meaningfully different from one another, at least for this particular choice of model and data set. This indicates that the uncertainty approximation itself may contain valueable information about the model’s confidence in its own predictions.

3.3 Class-specific uncertainty

If \(\hat{\sigma}_k\) captures model uncertainty, then we would expect the class-specific distributions of \(\hat{\sigma}_k\) to somehow echo the confusion matrix in section 3. Let \(\hat{\sigma}_j\) denote the class-specific uncertainty, where \(j \in \{\text{airplane},...,\text{truck}\}\) is the corresponding class label.

to_string <- as_labeller(c(
  "0" = "airplane", 
  "1" = "automobile", 
  "2" = "bird",
  "3" = "cat", 
  "4" = "deer", 
  "5" = "dog", 
  "6" = "frog", 
  "7" = "horse", 
  "8" = "ship", 
  "9" = "truck"))
unc_df <- df %>% 
  group_by(truth) %>% 
  summarise(mean_uncertainty = mean(uncertainty))
mean_df <- as.tibble(rep(mean(df$uncertainty), 10))
hist_class <- df %>% 
  ggplot(aes(x=uncertainty)) +
  geom_histogram(aes(y=..density.., fill=factor(truth)), alpha=.7, bins=50) +
  geom_vline(data=unc_df, aes(xintercept = mean_uncertainty, col=factor(truth)), lwd=.5, lty="dashed") +
  geom_vline(data=mean_df, aes(xintercept = value), lwd=.3, lty="dotted") +
  facet_wrap(~truth, nrow = 2, ncol = 5, drop=FALSE, labeller = to_string) +
  theme_bw() +
  theme(legend.position = "none") +
  ggtitle("Distributions of class uncertainty")
hist_class

As noted in section 3, the model clearly mistakes some cats for dogs and some dogs for cats. The confusion seems to be reflected in the relative distributions of \(\hat{\sigma}_{cat}\) and \(\hat{\sigma}_{dog}\).

The following boxplots give an idea of the spread of \(\hat{\sigma}_j\) for each class \(j\) after grouping by classification status:

to_string <- as_labeller(c(
  "0" = "airplane", 
  "1" = "automobile", 
  "2" = "bird",
  "3" = "cat", 
  "4" = "deer", 
  "5" = "dog", 
  "6" = "frog", 
  "7" = "horse", 
  "8" = "ship", 
  "9" = "truck"))
unc_df <- df %>% 
  group_by(truth) %>% 
  summarise(mean_uncertainty = mean(uncertainty))
box_class <- df %>% 
  ggplot(aes(y=uncertainty)) +
  geom_boxplot(aes(x=factor(correct), fill=factor(correct)), alpha=.7) +
  facet_wrap(~truth, nrow=2, ncol=5, labeller = to_string) +
  theme_bw() +
  theme(legend.position = "none") +
  ggtitle("Boxplots of class uncertainty") +
  labs(x="correct")
box_class

In summary, the class-specific approximations of uncertainty is consistent with the confusion matrix in section 3: Higher uncertainty seems to be associated with categories that tend to be mislabeled.

3.4 Relationship to other variables

As \(\hat{\mu}_k\) decreases, the softmax probabilities are spread out across the elements of the predictive mean vector \(\hat{\mu}\). Another view is that the number of candidate classes increases. Naively, we would therefore expect lower values of \(\hat{\mu}_k\) to be associated with higher uncertainty.

The following figure shows the relationship between \(\hat{\sigma}_k\) and \(\hat{\mu}_k\) (we have plotted a smoothed estimate of the mean uncertainty as a function of the prob1 output to make this clearer):

# Plotting softmax output of prediction against estimated uncertainty
p5 <- df %>% 
  ggplot(aes(x=prob1, y=uncertainty)) +
  geom_point(alpha=.2) +
  geom_smooth() +
  ggtitle("Uncertainty vs. softmax prediction") +
  labs(x="softmax output of predicted class") +
  theme_bw()
p5

The plot indicates a concave shape, which contradicts our naive assumption. A possible explanation is that the minimum value of \(\hat{\mu}_k\) is bounded below by \(0.1\). As \(\hat{\mu}_k \rightarrow 0.1\), all the other elements of the predictive mean vector \(\hat{\mu}_j \rightarrow 0.1\). This follows from the fact that \(\hat{\mu}_k = \text{argmax}_k \hat{\mu}\). Pursuing this line of thought, we speculate that the model most likely yields similar classification results for each stochastic forward pass when \(\hat{\mu}_k\) is low, which consequently leads to a lower estimate of \(\hat{\sigma}_k\) thus explaining why \(\hat{\sigma}_k\) decreases. This highlights a potential drawback of the ad hoc approximation given in section 1.1 : A classification that results in maximum uncertainty with respect to a measure such as entropy (i.e. when \(\hat{\mu}_j = 0.1\) for all \(j\)) could potentially be associated with a small empirical standard deviation \(\hat{\sigma}_k\).

Furthermore, \(\hat{\sigma}_k\) seems to peak around prob1 \(\approx 0.5\). Additional information can be leveraged by colour-coding the data points based on the value of the runner-up prediction prob2, as shown in the following figure:

# Plotting softmax output of prediction against estimated uncertainty, coloured by softmax output of runner-up
p7 <- df %>% 
  ggplot(aes(x=prob1, y=uncertainty)) +
  geom_point(aes(col=prob2), shape=21, alpha=.7) +
  geom_point(data=agg_df, aes(x=mean_prob1, y=mean_uncertainty, shape=as.logical(correct)), size=2.5) +
  #geom_point(data=agg_df, aes(y=uncertainty, x=mean_prob1, shape=as.logical(correct)), size=2) +
  ggtitle("Uncertainty vs. softmax output of prediction for all observations") +
  labs(x="softmax output of predicted class", shape="correct") +
  scale_color_distiller(name="Runner up",
                        palette = "Spectral") +
  scale_shape_discrete(name=expression(paste("(",bar(mu)["pred"],", ",bar(sigma)["pred"],")")),
                       labels=c("Incorrect", "Correct")) +
  theme_bw()
p7

A blue point corresponds to an observation with a low value of prob2, whereas a red point corresponds to an observation with a high value of prob2. Additionally, we have plotted the average mean and uncertainty for correctly (black dot) and incorrectly (black triangle) classified observations.

Clearly, the largest values of the prob2 cluster around prob1. This is to be expected, simply because when prob1 \(= 0.5\) we have a maximum of “left-over” probability available for distribution among the other classes in \(\hat{\mu}\). In other words, the value of prob2 is constrained by prob1. However, the maximum values of \(\hat{\sigma}_k\) appear to be associated with relatively large pairs of prob1 and prob2. This could suggest that uncertainty estimation by ad hoc methods such as \(\hat{\sigma}_k\) could be most useful in binary classification settings, or to detect situations with a small number of competing classes in a multilabel setting.

The observations can be partitioned by classification status and overlayed with a 2D kernel density estimate (KDE). The KDE gives an idea of the joint distribution of prob1 and prob2:

# Plotting uncertainty vs. softmax output of prediction
p8 <- df %>% 
  ggplot(aes(x=prob1, y=uncertainty)) +
  geom_point(aes(col=prob2),alpha=0.5) +
  geom_density_2d(col="black", alpha=.3) +
  ggtitle("Uncertainty vs. softmax output of prediction by incorrect/correct") +
  labs(x="softmax output of prediction") +
  facet_grid(.~as.factor(correct)) +
  scale_color_distiller(name="Runner up",
                        palette = "Spectral") +
  theme_bw()
p8

The black contour lines indicate where most of the points are concentrated. The plot on the left is for incorrect predictions. The right hand plot represents the correct predictions. For the correct predictions, it seems as if far more of the points are concentrated around high predicted output/low runner-up output/low uncertainty. For the incorrect classifications, most of the points are concentrated around the area where \(\hat{\sigma}_k\) peaks. This indicates that the approximated uncertainty estimates indeed contain valuable information in the incorrect cases.

3.4.1 Runner-up predictions

The following plot shows the relationship between uncertainty estimates and the softmax output of the runner-up prediction. Unsurprisingly, model uncertainty increases as the softmax output of the runner-up increases. We have plotted a smoothed estimate of the mean uncertainty as a function of the runner-up output to make this clearer:

# Plotting softmax output of runner-up against estimated uncertainty
p10 <- df %>% 
  ggplot(aes(x=prob2, y=uncertainty)) +
  geom_point(alpha=.2) +
  geom_smooth(method="loess") +
  labs(x="softmax output of runner-up") +
  ggtitle("Uncertainty vs. softmax output of runner-up") +
  theme_bw()
p10

3.5 Uncertainty-prediction correlation

As mentioned in section 2.2, the connection established between dropout neural networks and GPs are lost when applied to convolutional neural networks. Performing a logistic regression gives us a simple way of testing if the approximated uncertainty is a significant predictor of the model’s ability to predict correctly:

# Fitting logistic regression model to check significance of uncertainty
model_sd <- glm(as.factor(correct)~uncertainty, data=df, family = binomial(link="logit"))
summary(model_sd)

Call:
glm(formula = as.factor(correct) ~ uncertainty, family = binomial(link = "logit"), 
    data = df)

Deviance Residuals: 
    Min       1Q   Median       3Q      Max  
-2.6704   0.2409   0.3588   0.7100   2.0114  

Coefficients:
             Estimate Std. Error z value Pr(>|z|)    
(Intercept)   3.55249    0.07625   46.59   <2e-16 ***
uncertainty -15.40803    0.43250  -35.63   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 10236.6  on 9999  degrees of freedom
Residual deviance:  8467.6  on 9998  degrees of freedom
AIC: 8471.6

Number of Fisher Scoring iterations: 5

The coefficient associated with uncertainty is highly significant, indicating that the estimates leveraged from MC dropout may indeed be a useful quantification of predictive uncertainty.

4 Referral Criteria

The question is then: How do we determine a reasonable uncertainty value for referral to a human expert? As we saw in section 3.1.2, the mean uncertainty values of the incorrect predictions higher than for the correct predictions (0.1802444 vs. 0.1021673, respectively).

Naively, we could set the threshold for referral to the mean uncertainty of the incorrectly classified images:

# Counting number of correct/incorrect by uncertainty >= .18 
mean_unc <- df %>% 
  filter(correct==0) %>% 
  summarise(mean_unc=mean(uncertainty))
referral <- df %>% 
  filter(uncertainty>=mean_unc[1,1]) %>% 
  count(correct)
referral

The problem here is apparent: Many of the correctly classified images are associated with a relatively high level of uncertainty (in our case, this is due to the bimodality of the uncertainty distribution in section 3.2.1). We speculate that although uncertainty seems to contain valueable information, the relative uncertainties of the correct/incorrect observations (in this case) may be too small to differentiate which images should be referred to an expert. We may need to amplify the quantification of uncertainty in some way.

4.1 Usefulness of runner-up predictions

For the most uncertain incorrectly classified images the runner-up suggestions are non-sensical. Still, is there any information to be obtained from the runner-up predictions? What would happen to our overall accuracy if we used the runner-up predictions for all incorrect classifications?

# Counting classification accuracy if runner-up is equal to ground truth
class2_df <- df %>%
  mutate(correct=replace(correct, correct==0 & class2==truth, 1)) %>% 
  count(correct)
class2_df

Accuracy would rise to 0.9079. This indicates that there may be some valuable information to be gathered from the runner-up predictions.

runnerup_df <- df %>% 
  filter(correct==0) %>% 
  mutate(runnerup = ifelse(class2==truth, 1, 0))
mean_runnerup <- runnerup_df %>%
  group_by(runnerup) %>% 
  summarise(meanuncertainty = mean(uncertainty),
            meanprob1 = mean(prob1),
            meanprob2 = mean(prob2),
            n=n())
p11 <- runnerup_df %>% 
  ggplot(aes(x=uncertainty, group=factor(runnerup))) +
  geom_histogram(aes(y=..density.., fill=factor(runnerup)), position="identity", bins = 50, alpha=.5) +
  geom_density(aes(y=..density.., col=factor(runnerup)), alpha=.5) +
  geom_rug(aes(x=uncertainty, col=factor(runnerup)), alpha=.5) +
  geom_vline(data = mean_runnerup, aes(xintercept=meanuncertainty, col=factor(runnerup)), lty="dashed") +
  ggtitle("Distributions of uncertainty") +
  labs(color="Prediction",
       fill="Prediction") +
  scale_color_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  scale_fill_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  theme_bw() +
  theme(legend.position = c(.9,.85))
p11

p12 <- runnerup_df %>% 
  ggplot(aes(x=prob1, group=factor(runnerup))) +
  geom_density(aes(y=..density.., col=factor(runnerup)), alpha=.5) +
  geom_rug(aes(x=prob1, col=factor(runnerup)), alpha=.5) +
  geom_vline(data = mean_runnerup, aes(xintercept=meanprob1, col=factor(runnerup)), lty="dashed") +
  ggtitle("Distributions of softmax predictions") +
  labs(color="Prediction",
       fill="Prediction") +
  scale_color_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  scale_fill_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  theme_bw() +
  theme(legend.position = c(.9,.85))
p12

p13 <- runnerup_df %>% 
  ggplot(aes(x=prob2, group=factor(runnerup))) +
  geom_density(aes(y=..density.., col=factor(runnerup)), alpha=.5) +
  geom_rug(aes(x=prob2, col=factor(runnerup)), alpha=.5) +
  geom_vline(data = mean_runnerup, aes(xintercept=meanprob2, col=factor(runnerup)), lty="dashed") +
  ggtitle("Distributions of runner up softmax probabilities") +
  labs(color="Prediction",
       fill="Prediction") +
  scale_color_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  scale_fill_discrete(breaks=c("0", "1"),
                         labels=c("0: Incorrect", "1: Correct")) +
  theme_bw() +
  theme(legend.position = c(.9,.85))
p13

So how do we determine which images to take a closer look at?

4.2 Leveraging Runner-up Probabilities

One possible approach is to incorporate information from the value of \(\tau_{jk}\), which we introduced in section 2.5. Consider the following cases:

  • \(\tau_{kj} \approx 1\) means that diff and uncertainty are relatively similar. This happens if a) the models have failed to agree on a clear favourite (diff is small) but model uncertainty is low, or b) the models have a favourite (diff is large) but model uncertainty is high. Let’s call these referral predictions.

  • \(\tau_{kj} \to 0\) means that uncertainty is much larger than diff. These should represent uncertain predictions.

  • \(\tau_{kj} \to \infty\) means that uncertainty is much smaller than diff. These should represent non-referral predictions.

As we saw in section 3, the mean \(\tau_{jk}\) (given by mean_ratio) for the incorrectly classified images is 2.8112788 and 262.6516078 for the correctly classified images. Setting the referral threshold to the mean \(\tau_{jk}\) for the incorrect classifications (2.8112788), we get:

# Counting number of correct/incorrect by tau <= 2.8
mean_tau <- df %>% 
  filter(correct==0) %>% 
  summarise(mean_tau=mean(diff_sd_ratio))
  
referral_mean <- df %>% 
  filter(diff_sd_ratio <= mean_tau[1,1]) %>% 
  count(correct)
referral_mean

We run into the same problem as when we used the mean uncertainty: Many of the correctly predicted images would be referred, in fact more than when we used the uncertainty estimates. It is interesting to note, however, that we get far more referrals of incorrectly classified images. Again, this may indicate that \(\tau_{jk}\) is a useful measure of uncertainty.

Setting the referral rate of the mean \(\tau_{jk} \leq 1\) gives us the following:

# Counting number of correct/incorrect by tau <= 1
median_tau <- df %>% 
  filter(correct==0) %>% 
  summarise(median_tau=median(diff_sd_ratio))
referral_1 <- df %>% 
  filter(diff_sd_ratio <= 1) %>% 
  count(correct)
referral_1

This is a clear improvement over our first approach, in terms of the amount of referred images. 731 fewer incorrect images are referred compared to 1315 fewer correct images. This could indicate that \(\tau_{jk}\) is a useful quantification of uncertainty.

5 References

[1] Gal, Y. & Ghahramani, Z. Bayesian Convolutional Neural Networks with Bernoulli Approximate Variational Inference. arXiv: 1506.02158 (2015).

[2] Gal, Y. & Ghahramani, Z. Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning. arXiv: 1506.02142 (2015).

[3] Gal, Y. & Ghahramani, Z. Dropout as a Bayesian Approximation: Appendix. arXiv: 1506.02157 (2015).

[4] Leibig, C. & Allken, V. et. al. Leveraging uncertainty information from deep neural networks for disease detection. Scientific Reports volume 7, Article number: 17816 (2017).

[5] Hinton, G. & Srivastava, N. et. al. Improving neural networks by preventing co-adaptation of feature detectors. arXiv: 1207.0580 (2012).

[6] Leibig, C. & Allken, V. et. al. Leveraging uncertainty information from deep neural networks for disease detection: supplementary material. Scientific Reports volume 7, Article number: 17816 (2017).

[7] Smith, L., & Gal, Y. Understanding Measures of Uncertainty for Adversarial Example Detection. arXiv preprint arXiv:1803.08533. (2018)

LS0tCnRpdGxlOiAiREFUMjU5OiBBbiBFeHBsb3JhdG9yeSBEYXRhIEFuYWx5c2lzIG9mIEFwcHJveGltYXRlZCBVbmNlcnRhaW50eSBpbiBEZWVwIExlYXJuaW5nIgphdXRob3I6ICJTZWFuIE1lbGluZyBNdXJyYXkiCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgICB0b2M6IHllcwogIGh0bWxfbm90ZWJvb2s6CiAgICBudW1iZXJfc2VjdGlvbnM6IHllcwogICAgdG9jOiB5ZXMKICAgIGNvZGVfZm9sZGluZzogaGlkZQotLS0KCioqKgojIEludHJvZHVjdGlvbgoKVGhlIHN1Y2Nlc3Mgb2YgZGVlcCBsZWFybmluZyBtb2RlbHMgaGFzIHR5cGljYWxseSBiZWVuIG1lYXN1cmVkIGluIHRlcm1zIG9mIHRoZWlyIHByZWRpY3RpdmUgcG93ZXIsIGJ1dCB0aGV5IGhhdmUgbGFja2VkIGEgcHJpbmNpcGxlZCB3YXkgb2YgZXhwcmVzc2luZyB1bmNlcnRhaW50eSBhYm91dCB0aGVzZSBwcmVkaWN0aW9ucy4KCkluIG15IG1hc3RlcidzIHRoZXNpcyB3ZSBhcHBseSByZWNlbnQgaW5zaWdodHMgY29ubmVjdGluZyBkcm9wb3V0IG5ldXJhbCBuZXR3b3JrcyB0byBbQmF5ZXNpYW4gYXBwcm94aW1hdGUgdmFyaWF0aW9uYWwgaW5mZXJlbmNlIChWSSldKGh0dHBzOi8vYXJ4aXYub3JnL2Ficy8xNjAxLjAwNjcwKS4gVkkgaXMgdGVjaG5pcXVlIGZvciBhcHByb3hpbWF0aW5nIGludHJhY3RhYmxlIGludGVncmFscyB0aGF0IGFyaXNlIHdoZW4gbW9kZWxsaW5nIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIGluIEJheWVzaWFuIGluZmVyZW5jZSBhbmQgbWFjaGluZSBsZWFybmluZy4gR2FsIGV0LiBhbC4gWzEsIDIsIDNdIGhhdmUgc2hvd24gdGhhdCB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBvZiBhIE5OIGNhbiBiZSBhcHByb3hpbWF0ZWQgYnkgbGVhdmluZyBkcm9wb3V0IG9uIGF0IHRlc3QgdGltZSBhbmQgc2FtcGxpbmcgbXVsdGlwbGUgcHJlZGljdGlvbnMuIFRoaXMgYW1vdW50cyB0byBkcmF3aW5nIE1vbnRlIENhcmxvIChNQykgc2FtcGxlcyBmcm9tIHRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIChhIGJyaWVmIGRlc2NyaXB0aW9uIG9mIHRoaXMgcHJvY2VzcyBpcyBsaXN0ZWQgaW4gc2VjdGlvbiAxLjEpLiBUaGUgQmF5ZXNpYW4gZnJhbWV3b3JrIGFsbG93cyB1cyB0byBvYnRhaW4gcHJpbmNpcGxlZCB1bmNlcnRhaW50eSBlc3RpbWF0ZXMgd2hlbiBtYWtpbmcgcHJlZGljdGlvbnMgaW4gdGhlc2Ugc28gY2FsbGVkICpNQyBkcm9wb3V0KiBOTnMuIAoKVGhlIHJlc3VsdHMgb2YgWzEsMiwzXSBzZWVtIHBhcnRpY3VsYXJseSBwcm9taXNpbmcgd2hlbiBhcHBsaWVkIHRvIGhlYWx0aGNhcmUuIEluIGZhY3QsIGEgcmVjZW50IHBhcGVyIHB1Ymxpc2hlZCBpbiBOYXR1cmUgWzRdIGFwcGxpZXMgTUMgZHJvcG91dCB0byBjYXB0dXJlIHVuY2VydGFpbnR5IGVzdGltYXRlcyB3aGVuIHByZWRpY3RpbmcgdGhlIHByZXNlbmNlIG9mIGRpYWJldGljIHJldGlub3BhdGh5IGluIHBhdGllbnRzLiBUaGlzIHBhcGVyIGRlbW9uc3RyYXRlcyBob3cgdW5jZXJ0YWludHkgZXN0aW1hdGVzIGNhbiBwcm92aWRlIHVzZWZ1bCBpbmZvcm1hdGlvbiB0byB0aGUgY2xpbmljaWFuIHRhc2tlZCB3aXRoIGludGVycHJldGluZyB0aGUgcmVzdWx0cyBvZiBtZWRpY2FsIGltYWdlcy4gVGhlIGtleSBpZGVhIGlzIHRoYXQgdGhpcyBodW1hbi1tYWNoaW5lIGludGVyYWN0aW9uIHdpbGwgbGVhZCB0byBvdmVyYWxsIGJldHRlciByZXN1bHRzIHRoYW4gZWl0aGVyIGNvdWxkIHByb2R1Y2UgaW5kaXZpZHVhbGx5LgoKSW4gdGhpcyBub3RlYm9vayBJIHdpbGwgZmlyc3QgYnJpZWZseSBpbnRyb2R1Y2UgdGhlIGdlbmVyYWwgaWRlYSBiZWhpbmQgTUMgZHJvcG91dC4gVGhlbiB3ZSB3aWxsIGRlbW9uc3RyYXRlIGhvdyBNQyBkcm9wb3V0IGhhcyBiZWVuIGFwcGxpZWQgaW4gZXhpc3RpbmcgbGl0ZXJhdHVyZSB0aHJvdWdoIGEgcHJhY3RpY2FsIGV4YW1wbGUuIFdlIHdpbGwgdXNlIHRoZSBgZmFzdGFpYCBmcmFtZXdvcmssIGFuZCB0aGUgZ29hbCBpcyB0byBlc3RpbWF0ZSB1bmNlcnRhaW50eSBvbiBhIGNsYXNzaWZpY2F0aW9uIHRhc2sgYmFzZWQgb24gdGhlIGNvbGxlY3Rpb24gb2YgbGFiZWxsZWQgaW1hZ2VzIGluIHRoZSBbQ0lGQVItMTAgZGF0YSBzZXRdKGh0dHBzOi8vd3d3LmNzLnRvcm9udG8uZWR1L35rcml6L2NpZmFyLmh0bWwpLgoKIyMgQmFja2dyb3VuZAoKQSBuZXVyYWwgbmV0d29yayBpcyBtYWRlIHVwIG9mIG1hbnkgbmV1cm9ucyB3aGljaCBhcmUgb3JnYW5pemVkIGluIGxheWVycy4gTmV1cm9ucyBhcmUgb2Z0ZW4gY2FsbGVkIG5vZGVzIG9yIHVuaXRzLCBkZXBlbmRpbmcgb24geW91ciBjaG9pY2Ugb2YgbWFjaGluZSBsZWFybmluZyBsaXRlcmF0dXJlLiBIZW5jZWZvcnRoIHdlIHdpbGwgcmVmZXIgdG8gdGhlbSBhcyB1bml0cy4gCgpJbiBhIHR5cGljYWwgbmV1cmFsIG5ldHdvcmsgdGhlcmUgYXJlIG1hbnksIG1hbnkgdW5pdHMuIEFzIGEgY29uc2VxdWVuY2UgdGhlIG51bWJlciBvZiBwYXJhbWV0ZXJzIGdyZWF0bHkgZXhjZWVkcyB0aGUgbnVtYmVyIG9mIGRhdGEgcG9pbnRzLCBkcmFtYXRpY2FsbHkgaW5jcmVhc2luZyB0aGUgcmlzayBvZiBvdmVyZml0dGluZyAoaS5lLiB0aGVyZSBhcmUgbWFueSBzZXR0aW5ncyBvZiB3ZWlnaHRzIHdoaWNoIHdpbGwgY2F1c2UgdGhlIG5ldHdvcmsgdG8gZml0IHRoZSBkYXRhIGFsbW9zdCBwZXJmZWN0bHkpLgoKRHJvcG91dCBpcyBhIGNvbW1vbiBzdG9jaGFzdGljIHJlZ3VsYXJpc2F0aW9uIHRlY2huaXF1ZSBbNV0gdGhhdCBpcyB1c2VkIHRvIHByZXZlbnQgb3ZlcmZpdHRpbmcgaW4gbmV1cmFsIG5ldHdvcmtzLiBUaGUgdGVybSBkcm9wb3V0IHJlZmVycyB0byByYW5kb21seSAiZHJvcHBpbmcgb3V0IiBub25vdXRwdXQgdW5pdHMsIHRlbXBvcmFyaWx5IHJlbW92aW5nIGFsbCBjb25uZWN0aW9ucyB0byB0aGUgcmVzdCBvZiB0aGUgbmV0d29yay4gVGhlIG1haW4gaWRlYSBpcyB0aGF0IGlmIHRoZSBwcmVzZW5jZSBvZiBvdGhlciB1bml0cyBpcyB1bnJlbGlhYmxlLCBlYWNoIHVuaXQgaXMgZm9yY2VkIHRvIGxlYXJuIGhvdyB0byBiZSB1c2VmdWwgb24gaXRzIG93bi4gQXQgdGVzdCB0aW1lIGFsbCB1bml0cyBhcmUgYWN0aXZhdGVkLCBhbmQgdGhlIHdlaWdodHMgb2YgdGhlIG5ldHdvcmsgYXJlIHNjYWxlZCBieSB0aGUgZHJvcG91dCByYXRlIGluIG9yZGVyIHRvIG1hdGNoIHRoZSBleHBlY3RlZCBvdXRwdXQgZHVyaW5nIHRyYWluaW5nLgoKUmVjZW50IHdvcmsgYnkgR2FsIGV0LiBhbC4gWzEsIDIsIDNdIGNhc3RzIGRyb3BvdXQgbmV1cmFsIG5ldHdvcmtzIGFzIGFwcHJveGltYXRlIEJheWVzaWFuIGluZmVyZW5jZS4gVGhlaXIgcmVzdWx0cyBzaG93IHRoYXQgdGhlIHByZWRpY3RpdmUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBvZiBhIG5ldXJhbCBuZXR3b3JrIGNhbiBiZSBhcHByb3hpbWF0ZWQgYnkgbGVhdmluZyBkcm9wb3V0IG9uIGF0IHRlc3QgdGltZS4gCgpDb25zaWRlciBhIGNsYXNzaWZpY2F0aW9uIHNldHRpbmcsIHN1Y2ggYXMgaW4gQ0lGQVItMTAuIEVzc2VudGlhbGx5LCB3aGF0IGhhcHBlbnMgd2hlbiBhcHBseWluZyBNQyBkcm9wb3V0IGlzIHRoZSBmb2xsb3dpbmc6CgoqIEFuIGltYWdlIGlzIGZlZCBmb3J3YXJkIHRocm91Z2ggdGhlIG5ldHdvcmsgJFQkIHRpbWVzICh3ZSB1c2UgJFQ9MTAwJCBhcyByZWNvbW1lbmRlZCBpbiBbNF0pLiBFYWNoIHRpbWUgdGhlIGltYWdlIGlzIGZlZCB0aHJvdWdoIGlzIGNhbGxlZCBhICpzdG9jaGFzdGljIGZvcndhcmQgcGFzcyouCiogRm9yIGVhY2ggc3RvY2hhc3RpYyBmb3J3YXJkIHBhc3MsIGEgc2xpZ2h0bHkgZGlmZmVyZW50IG5ldHdvcmsgaXMgbWFraW5nIHByZWRpY3Rpb25zIGJlY2F1c2UgZHJvcG91dCBoYXMgcmFuZG9tbHkgc3dpdGNoZWQgb2ZmIHVuaXRzLiAKKiBBcyBhIHJlc3VsdCBlYWNoIHN0b2NoYXN0aWMgZm9yd2FyZCBwYXNzIHJldHVybnMgMTAwIHNsaWdodGx5IGRpZmZlcmVudCB2ZWN0b3JzIG9mIGNsYXNzIHByZWRpY3Rpb25zLgoqIFRvIG1ha2UgYSBwcmVkaWN0aW9uIHdlIGF2ZXJhZ2UgdGhlIDEwMCB2ZWN0b3JzLiBUaGUgaXMgY2FsbGVkIHRoZSAqKnByZWRpY3RpdmUgbWVhbioqIHZlY3RvciwgZGVub3RlZCBieSAkXGhhdHtcbXV9JC4gVGhlIGNsYXNzIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGxhcmdlc3QgZWxlbWVudCBpbiB0aGUgcmVzdWx0aW5nIHZlY3RvciBpcyBvdXIgZmluYWwgcHJlZGljdGlvbiwgaS5lLiAkcCh5PWt8WCx3KSA9IFx0ZXh0e2FyZ21heH1fayBcaGF0e1xtdX0kLgoqIEZpbmFsbHkgd2UgY2FsY3VsYXRlIHRoZSBzdGFuZGFyZCBkZXZpYXRpb24gaW4gY2xhc3MgcHJlZGljdGlvbnMgb3ZlciBhbGwgZm9yd2FyZCBwYXNzZXMuIFRoaXMgaXMgb3VyIGVzdGltYXRlZCB1bmNlcnRhaW50eS4KCkdhbCBldC4gYWwuIFszXSBzaG93IHRoYXQgdGhlIGFib3ZlIGFtb3VudHMgdG8gZHJhd2luZyBNb250ZSBDYXJsbyBzYW1wbGVzIGZyb20gdGhlIHByZWRpY3RpdmUgcG9zdGVyaW9yLiBUaGVpciB3b3JrIGRlbW9uc3RyYXRlcyB0aGF0IGFwcGx5aW5nIGRyb3BvdXQgaXMgZWZmZWN0aXZlbHkgdGhlIHNhbWUgYXMgZGVmaW5pbmcgYSAqQmF5ZXNpYW4gbmV1cmFsIG5ldHdvcmsqIHdpdGggYSBCZXJub3VsbGkgYXBwcm94aW1hdGluZyBwcmlvciBvdmVyIHRoZSBwYXJhbWV0ZXJzLiBbR2FsIGhhcyB3cml0dGVuIGFuIGV4Y2VsbGVudCBibG9nIHBvc3QgdGhhdCBpbnRyb2R1Y2VzIHRoZSB3b3JrXShodHRwOi8vbWxnLmVuZy5jYW0uYWMudWsveWFyaW4vYmxvZ18zZDgwMWFhNTMyYzFjZS5odG1sKSBhbmQgdGhlIGRlcml2YXRpb24uCgpJbiBwcmFjdGljYWwgYXBwbGljYXRpb25zIFs0XSwgbW9kZWwgdW5jZXJ0YWlueSBpcyBhcHByb3hpbWF0ZWQgYnkgdGhlIGVtcGlyaWNhbCBzdGFuZGFyZCBkZXZpYXRpb24gb2YgdGhlIHByZWRpY3Rpb25zIGZvciBjbGFzcyAkayQsIGkuZS4gJCRcaGF0e1xzaWdtYX1fayA9IFxzcXJ0e1xmcmFje1xzdW1fe3Q9MX1eVHtbcF90KGt8WCx3KSAtIFxoYXR7XG11fV9rfV1eMn17VC0xfX0kJCB3aGVyZSAkJFxoYXR7XG11fV9rID0gXGZyYWN7MX17VH1cc3VtX3t0PTF9XlQgcF90KGt8WCx3KSQkIGlzIHRoZSBhdmVyYWdlZCBzb2Z0bWF4IG91dHB1dHMgb2YgdGhlIHByZWRpY3RlZCBjbGFzcy4gVGhpcyBpcyBhIHNvbWV3aGF0IGFkIGhvYyBhcHByb3hpbWF0aW9uLCBidXQgcmVjZW50IHJlc2VhcmNoIHN1Z2dlc3RzIHRoYXQgJFxoYXR7XHNpZ21hfV9rJCBpcyBhIG1lYW5pbmdmdWwgdW5jZXJ0YWludHkgZXN0aW1hdGUgWzddLgoKIyMgUHJvYmxlbSBzdGF0ZW1lbnQKClRoZSBkZXJpdmF0aW9uIGluIEdhbCBldC4gYWwuIFsyXSBpcyBiYXNlZCBvbiB0aGUgb2JzZXJ2YXRpb24gdGhhdCBhIHNoYWxsb3cgbmV1cmFsIG5ldHdvcmsgd2l0aCBpbmZpbml0ZWx5IG1hbnkgd2VpZ2h0cyBjb252ZXJnZXMgdG8gYSBHYXVzc2lhbiBwcm9jZXNzIChHUCkgd2l0aCBhIHNwZWNpZmljIGNvdmFyaWFuY2UgZnVuY3Rpb24uIEEgR1AgaXMgYSBub24tcGFyYW1ldHJpYywgcHJvYmFiaWxpc3RpYyBtYWNoaW5lIGxlYXJuaW5nIG1ldGhvZC4gVGhlIGlkZWEgaXMgdGhhdCB3ZSBwbGFjZSBhIHByaW9yIGRpc3RyaWJ1dGlvbiBvdmVyIHRoZSBmdW5jdGlvbiBzcGFjZSwgYW5kIGJ5IG9ic2VydmluZyBuZXcgZGF0YSBwb2ludHMgd2UgY2FuIGZpZ3VyZSBvdXQgd2hpY2ggZnVuY3Rpb24gaXMgbW9zdCBsaWtlbHkgdG8gaGF2ZSBnZW5lcmF0ZWQgdGhlIG9ic2VydmVkIGRhdGEuIEEgR1AgaXMgZnVsbHkgc3BlY2lmaWVkIGJ5IGl0cyBtZWFuIGFuZCBjb3ZhcmlhbmNlIGZ1bmN0aW9ucywgYW5kIGFsbG93cyB1cyB0byBvYnRhaW4gdW5jZXJ0YWludHkgZXN0aW1hdGVzIFsxXS4gVGhlIGV4dGVuc2lvbiBvZiB0aGlzIHRvIGRyb3BvdXQgbmV1cmFsIG5ldHdvcmtzIGlzIHRoZSBtYWluIHJlc3VsdCBvZiBHYWwgZXQuIGFsLiBbMl0uCgpJbiBbMV0gaG93ZXZlciwgR2FsIGV0LiBhbC4gZXh0ZW5kIHRoaXMgaWRlYSBmdXJ0aGVyIHRvIGluY2x1ZGUgcHJpb3JzIG92ZXIgdGhlIHdlaWdodHMgb2YgdGhlIGNvbnZvbHV0aW9uYWwgbGF5ZXJzIGluIGEgY29udm9sdXRpb25hbCBuZXVyYWwgbmV0d29yayAoQ05OKS4gQSBDTk4gaXMgYSBzcGVjaWFsaXplZCB0eXBlIG9mIG5ldXJhbCBuZXR3b3JrLCB1c2VkIHByaW1hcmlseSBhbmQgdmVyeSBlZmZlY3RpdmVseSBmb3IgaW1hZ2UgYW5hbHlzaXMuIFRoZSBhdXRob3JzIGJyaWVmbHkgc3RhdGUgdGhhdCB0aGUgR1AgaW50ZXJwcmV0YXRpb24gaXMgbG9zdCB3aGVuIHRoZSBtb2RlbCBpcyBleHRlbmRlZCB0byBDTk5zLCBidXQgdGhhdCB0aGVzZSBuZXR3b3JrcyBzdGlsbCBjYW4gYmUgIm1vZGVsbGVkIGFzIEJheWVzaWFuIi4KCkFzIGZhciBhcyB3ZSBhcmUgYXdhcmUsIHRoZXJlIGhhdmUgYmVlbiBubyBlZmZvcnRzIHRvIGRldGVybWluZSB0aGUgY29ycmVsYXRpb24gYmV0d2VlbiB0aGUgYXBwcm94aW1hdGVkIHVuY2VydGFpbnR5IGFuZCBhIG5ldHdvcmsncyBhYmlsaXR5IHRvIHByZWRpY3QgY29ycmVjdGx5LiBNb3Jlb3ZlciwgdGhlIHdvcmsgZG9uZSBzbyBmYXIgc2VlbXMgdG8gZm9jdXMgb24gdGhlIHVuY2VydGFpbnR5IGFzc29jaWF0ZWQgd2l0aCB0aGUgcHJlZGljdGVkIGNsYXNzLiBJbiBvdGhlciB3b3Jkcywgb3VyIHByb2JsZW0gc3RhdGVtZW50IGlzOgoKPiAqQXJlIHRoZSB1bmNlcnRhaW50eSBhcHByb3hpbWF0aW9ucyBvYnRhaW5lZCBieSBhcHBseWluZyBNb250ZSBDYXJsbyBkcm9wb3V0IHRvIGNvbnZvbHV0aW9uYWwgbmV1cmFsIG5ldHdvcmtzIGEgcmVhc29uYWJsZSBtZWFzdXJlIG9mIG1vZGVsIHVuY2VydGFpbnR5PyoKCldlIHdpbGwgYWxzbyBleGFtaW5lIGlmIHRoZXJlIGlzIGFueSBhZGRpdGlvbmFsIGluZm9ybWF0aW9uIHRvIGJlIGdhaW5lZCBmcm9tIGVzdGFibGlzaGluZyBhIGNvbm5lY3Rpb24gYmV0d2VlbiB0aGUgcHJlZGljdGlvbiBhbmQgdGhlICpydW5uZXItdXAqIHByZWRpY3Rpb24uCgojIFNldHVwCkluIHRoaXMgbm90ZWJvb2sgd2UgdXNlIHRoZSBmb2xsb3dpbmcgUiBwYWNrYWdlczogYHRpZHl2ZXJzZWAgYW5kIGBnZ3Bsb3QyYC4gSW4gYWRkaXRpb24gd2UgdXNlIHRoZSBgbXVsdGlwbG90YCBmdW5jdGlvbmFsaXR5IHByb3ZpZGVkIGJ5IFtDb29rYm9vayBmb3IgUl0oaHR0cDovL3d3dy5jb29rYm9vay1yLmNvbS9HcmFwaHMvTXVsdGlwbGVfZ3JhcGhzX29uX29uZV9wYWdlXyhnZ3Bsb3QyKS8pLiBJbiBQeXRob24gd2UgdXNlIGBmYXN0YWlgLCBgbnVtcHlgIGFuZCBgcGFuZGFzYC4gRnVsbCBjb2RlIGZvciB0cmFpbmluZyBhbmQgaW5mZXJlbmNlIFthdmFpbGFibGUgYXQgR2l0SHViXShsaW5rKS4gQWxsIGNvZGUgZm9yIHRoZSBleHBsb3JhdG9yeSBkYXRhIGFuYWx5c2lzIGlzIGluY2x1ZGVkIGluIHRoaXMgZG9jdW1lbnQuCgpgYGB7ciBlY2hvPUZBTFNFLCByZXN1bHRzPSdoaWRlJ30KIyBMb2FkaW5nIHVzZWZ1bCBwYWNrYWdlcwpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KGNhcmV0KQoKIyBNdWx0aXBsZSBwbG90IGZ1bmN0aW9uCiMKIyBnZ3Bsb3Qgb2JqZWN0cyBjYW4gYmUgcGFzc2VkIGluIC4uLiwgb3IgdG8gcGxvdGxpc3QgKGFzIGEgbGlzdCBvZiBnZ3Bsb3Qgb2JqZWN0cykKIyAtIGNvbHM6ICAgTnVtYmVyIG9mIGNvbHVtbnMgaW4gbGF5b3V0CiMgLSBsYXlvdXQ6IEEgbWF0cml4IHNwZWNpZnlpbmcgdGhlIGxheW91dC4gSWYgcHJlc2VudCwgJ2NvbHMnIGlzIGlnbm9yZWQuCiMKIyBJZiB0aGUgbGF5b3V0IGlzIHNvbWV0aGluZyBsaWtlIG1hdHJpeChjKDEsMiwzLDMpLCBucm93PTIsIGJ5cm93PVRSVUUpLAojIHRoZW4gcGxvdCAxIHdpbGwgZ28gaW4gdGhlIHVwcGVyIGxlZnQsIDIgd2lsbCBnbyBpbiB0aGUgdXBwZXIgcmlnaHQsIGFuZAojIDMgd2lsbCBnbyBhbGwgdGhlIHdheSBhY3Jvc3MgdGhlIGJvdHRvbS4KIwptdWx0aXBsb3QgPC0gZnVuY3Rpb24oLi4uLCBwbG90bGlzdD1OVUxMLCBmaWxlLCBjb2xzPTEsIGxheW91dD1OVUxMKSB7CiAgbGlicmFyeShncmlkKQoKICAjIE1ha2UgYSBsaXN0IGZyb20gdGhlIC4uLiBhcmd1bWVudHMgYW5kIHBsb3RsaXN0CiAgcGxvdHMgPC0gYyhsaXN0KC4uLiksIHBsb3RsaXN0KQoKICBudW1QbG90cyA9IGxlbmd0aChwbG90cykKCiAgIyBJZiBsYXlvdXQgaXMgTlVMTCwgdGhlbiB1c2UgJ2NvbHMnIHRvIGRldGVybWluZSBsYXlvdXQKICBpZiAoaXMubnVsbChsYXlvdXQpKSB7CiAgICAjIE1ha2UgdGhlIHBhbmVsCiAgICAjIG5jb2w6IE51bWJlciBvZiBjb2x1bW5zIG9mIHBsb3RzCiAgICAjIG5yb3c6IE51bWJlciBvZiByb3dzIG5lZWRlZCwgY2FsY3VsYXRlZCBmcm9tICMgb2YgY29scwogICAgbGF5b3V0IDwtIG1hdHJpeChzZXEoMSwgY29scyAqIGNlaWxpbmcobnVtUGxvdHMvY29scykpLAogICAgICAgICAgICAgICAgICAgIG5jb2wgPSBjb2xzLCBucm93ID0gY2VpbGluZyhudW1QbG90cy9jb2xzKSkKICB9CgogaWYgKG51bVBsb3RzPT0xKSB7CiAgICBwcmludChwbG90c1tbMV1dKQoKICB9IGVsc2UgewogICAgIyBTZXQgdXAgdGhlIHBhZ2UKICAgIGdyaWQubmV3cGFnZSgpCiAgICBwdXNoVmlld3BvcnQodmlld3BvcnQobGF5b3V0ID0gZ3JpZC5sYXlvdXQobnJvdyhsYXlvdXQpLCBuY29sKGxheW91dCkpKSkKCiAgICAjIE1ha2UgZWFjaCBwbG90LCBpbiB0aGUgY29ycmVjdCBsb2NhdGlvbgogICAgZm9yIChpIGluIDE6bnVtUGxvdHMpIHsKICAgICAgIyBHZXQgdGhlIGksaiBtYXRyaXggcG9zaXRpb25zIG9mIHRoZSByZWdpb25zIHRoYXQgY29udGFpbiB0aGlzIHN1YnBsb3QKICAgICAgbWF0Y2hpZHggPC0gYXMuZGF0YS5mcmFtZSh3aGljaChsYXlvdXQgPT0gaSwgYXJyLmluZCA9IFRSVUUpKQoKICAgICAgcHJpbnQocGxvdHNbW2ldXSwgdnAgPSB2aWV3cG9ydChsYXlvdXQucG9zLnJvdyA9IG1hdGNoaWR4JHJvdywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsYXlvdXQucG9zLmNvbCA9IG1hdGNoaWR4JGNvbCkpCiAgICB9CiAgfQp9CgojIERhdGEgY2xlYW5pbmcgZnVuY3Rpb24KcHJvY2VzcyA8LSBmdW5jdGlvbihST09ULCBmaWxlbmFtZSwgbmFtZSwga2VybmVsX3N6LCBkcm9wX3JhdGUpewogIFJPT1QgPC0gIn4vRG9jdW1lbnRzL01hc3Rlcm9wcGdhdmUvRGF0YS9SZXN1bHRhdGVyLyIKICBQQVRIIDwtIHBhc3RlKFJPT1QsIGZpbGVuYW1lLCBzZXA9IiIpCiAgZGF0IDwtIGFzLnRpYmJsZShyZWFkLmNzdihhcy5jaGFyYWN0ZXIoUEFUSCkpKQogICNkYXQgPC0gc2VsZWN0KGRhdCwgLVgpCiAgZGF0IDwtIGRhdCAlPiUgCiAgICBtdXRhdGUobW9kZWw9bmFtZSwKICAgICAgICAgICBrZXJuZWw9a2VybmVsX3N6LAogICAgICAgICAgIGRyb3BvdXQ9ZHJvcF9yYXRlKQogIHJldHVybihkYXQpCn0KYGBgCgojIyBFeHBlcmltZW50YWwgc2V0dXB7LnRhYnNldH0KClN0YXRlLW9mLXRoZS1hcnQgYXJjaGl0ZWN0dXJlcyBzdWNoIGFzIFJlc05ldCBhbmQgRGVuc2VOZXQgYXJlIHZlcnkgcG93ZXJmdWwsIGJ1dCB0aGV5IGFyZSBhbHNvIGNvbXBsaWNhdGVkIGFuZCB0aGVpciBpbm5lciB3b3JraW5ncyBhcmUgcXVpdGUgY29udm9sdXRlZC4gV2UgYXJlIHByaW1hcmlseSBpbnRlcmVzdGVkIGluIGV4YW1pbmluZyB0aGUgY29ycmVsYXRpb24gYmV0d2VlbiB1bmNlcnRhaW50eSBlc3RpbWF0aW9uIGFuZCBwcmVkaWN0aXZlIGNhcGFiaWxpdGllcy4gSXQgaXMgYXJndWFibHkgYmV0dGVyIHRvIHVzZSBhIHNpbXBsZSBuZXR3b3JrIGFyY2hpdGVjdHVyZSB0byBpbGx1c3RyYXRlIHRoZSBpZGVhIG9mIE1DIGRyb3BvdXQuIEluIG91ciBhcHByb2FjaCB3ZSB1c2UgTGVOZXQtNS4gQ2xpY2sgb24gdGhlIHRhYnMgZm9yIGltcGxlbWVudGF0aW9uIGRldGFpbHMuIEZ1bGwgY29kZSBpcyBhdmFpbGFibGUgb24gW0dpdEh1Yl0obGluaykuIEluIHRoZSBmb2xsb3dpbmcgd2UgYXNzdW1lIGJhc2ljIGZhbWlsaWFyaXR5IHdpdGggTk5zIGFuZCBzcGVjaWZpY2FsbHkgQ05Ocy4gKipOT1RFOiBDbGljayBvbiBDb2RlLXRhYiB0byBleHBhbmQgY2h1bmtzLioqCgojIyMgTW9kZWwKCkxlTmV0LTUgd2FzIGEgcGlvbmVlcmluZyA3LWxheWVyIGNvbnZvbHV0aW9uYWwgbmV1cmFsIG5ldHdvcmsgb3JpZ2luYWxseSBkZXZlbG9wZWQgYnkgWWFubiBMZUN1bm4gaW4gMTk5OCBmb3IgaGFuZHdyaXR0ZW4gZGlnaXQgcmVjb2duaXRpb24uIEl0IGlzIGhvcGVsZXNzbHkgcHJpbWl0aXZlIGNvbXBhcmVkIHRvIGNvbnRlbXBvcmFyeSBhcmNoaXRlY3R1cmVzLCBidXQgaXMgdmVyeSB1c2VmdWwgZm9yIGV4cGVyaW1lbnRhdGlvbiBhbmQgcHJvb2Ytb2YtY29uY2VwdCB3b3JrIGR1ZSB0byBpdCdzIHNpbXBsaWNpdHkuIFRoZSBmb2xsb3dpbmcgY2h1bmsgc2hvd3MgdGhlIG1vZGVsIGFyY2hpdGVjdHVyZToKCmBgYHtweXRob24gcHl0aG9uLnJldGljdWxhdGU9RkFMU0UsIGV2YWw9RkFMU0V9CmNsYXNzIGxlbmV0X2FsbChubi5Nb2R1bGUpOgogICAgZGVmIF9faW5pdF9fKHNlbGYsIGNvbnZfc2l6ZT1jb252X3NpemUsIHBvb2xfc2l6ZT0yLCBkcm9wX3JhdGU9cCk6CiAgICAgICAgc3VwZXIoKS5fX2luaXRfXygpCiAgICAgICAgc2VsZi5kcm9wX3JhdGUgPSBkcm9wX3JhdGUKICAgICAgICBzZWxmLmNvbnYxID0gbm4uQ29udjJkKGluX2NoYW5uZWxzPTMsIG91dF9jaGFubmVscz0xOTIsIGtlcm5lbF9zaXplPWNvbnZfc2l6ZSkKICAgICAgICBzZWxmLmRyb3BtYzEgPSBEcm9wb3V0TUMocCkKICAgICAgICBzZWxmLnBvb2wxID0gbm4uTWF4UG9vbDJkKGtlcm5lbF9zaXplPXBvb2xfc2l6ZSwgc3RyaWRlPTIpCiAgICAgICAgc2VsZi5jb252MiA9IG5uLkNvbnYyZChpbl9jaGFubmVscz0xOTIsIG91dF9jaGFubmVscz0xOTIsIGtlcm5lbF9zaXplPWNvbnZfc2l6ZSwgcGFkZGluZz0yKQogICAgICAgIHNlbGYuZHJvcG1jMiA9IERyb3BvdXRNQyhwKQogICAgICAgIHNlbGYucG9vbDIgPSBubi5NYXhQb29sMmQoa2VybmVsX3NpemU9cG9vbF9zaXplLCBzdHJpZGU9MikKICAgICAgICBzZWxmLmRlbnNlMSA9IG5uLkxpbmVhcihpbl9mZWF0dXJlcz03KjcqMTkyLCBvdXRfZmVhdHVyZXM9MTAwMCkKICAgICAgICBzZWxmLmRyb3BtYzMgPSBEcm9wb3V0TUMocCkKICAgICAgICBzZWxmLmRlbnNlMiA9IG5uLkxpbmVhcihpbl9mZWF0dXJlcz0xMDAwLCBvdXRfZmVhdHVyZXM9MTApCiAgICAgICAgCiAgICBkZWYgZm9yd2FyZChzZWxmLCB4KToKICAgICAgICB4ID0gc2VsZi5kcm9wbWMxKHNlbGYuY29udjEoeCkpCiAgICAgICAgeCA9IHNlbGYucG9vbDEoeCkKICAgICAgICB4ID0gc2VsZi5kcm9wbWMyKHNlbGYuY29udjIoeCkpCiAgICAgICAgeCA9IHNlbGYucG9vbDIoeCkKICAgICAgICB4ID0geC52aWV3KHguc2l6ZSgwKSwgLTEpCiAgICAgICAgeCA9IHNlbGYuZHJvcG1jMyhGLnJlbHUoc2VsZi5kZW5zZTEoeCkpKSAgICAgICAKICAgICAgICB4ID0gc2VsZi5kZW5zZTIoeCkKICAgICAgICAKICAgICAgICByZXR1cm4geApgYGAKPGJyPgoKIyMjIE1DIGRyb3BvdXQgbGF5ZXIKCk91ciBzcGVjaWZpY2F0aW9uIG9mIExlTmV0LTUgZGlmZmVycyBmcm9tIHRoZSBvcmdpbmlhbCBpbiBvbmUgY3J1Y2lhbCB3YXk6IFdlIHVzZSBNQyBkcm9wb3V0IGxheWVycy4gTUMgZHJvcG91dCBpcyBub3QgYSBmZWF0dXJlIHRoYXQgaXMgaW1wbGVtZW50ZWQgaW4gUHlUb3JjaCwgYW5kIHdlIG11c3QgdGhlcmVmb3JlIGltcGxlbWVuZXQgc3VjaCBhIGxheWVyIG91cnNlbHZlcy4gRm9ydHVuYXRlbHksIHRoaXMgYW1vdW50cyB0byBhIHNpbXBsZSBhZGp1c3RtZW50IG9mIGV4aXN0aW5nIGNvZGUuIFdlIG1vZGlmeSB0aGUgYERyb3BvdXRgIGNsYXNzIHRvIHRha2UgYW4gYWRkaXRpb25hbCBhcmd1bWVudCBjYWxsZWQgYGRyb3BvdXRNQ2Agd2l0aCBkZWZhdWx0IHZhbHVlIHNldCB0byBgVHJ1ZWA6CgpgYGB7cHl0aG9uIHB5dGhvbi5yZXRpY3VsYXRlPUZBTFNFLCBldmFsPUZBTFNFfQpjbGFzcyBEcm9wb3V0TUMobm4uTW9kdWxlKToKICAgIHIiIiIKICAgIE1vZGlmaWVkIHZlcnNpb24gb2YgRHJvcG91dCBmcm9tIHRvcmNoL25uL21vZHVsZXMvZHJvcG91dC5weQogICAgQXJnczoKICAgICAgICBwOiBwcm9iYWJpbGl0eSBvZiBhbiBlbGVtZW50IHRvIGJlIHplcm9lZC4gRGVmYXVsdDogMC41CiAgICAgICAgZHJvcG91dE1DOiBJZiBzZXQgdG8gYGBUcnVlYGAsIGRyb3BvdXQgaXMgdHVybmVkIG9uIGF0IHRlc3QgdGltZS4gRGVmYXVsdDogYGBUcnVlYAogICAgICAgIGlucGxhY2U6IElmIHNldCB0byBgYFRydWVgYCwgd2lsbCBkbyB0aGlzIG9wZXJhdGlvbiBpbi1wbGFjZS4gRGVmYXVsdDogYGBGYWxzZWBgCiAgICBTaGFwZToKICAgICAgICAtIElucHV0OiBgQW55YC4gSW5wdXQgY2FuIGJlIG9mIGFueSBzaGFwZQogICAgICAgIC0gT3V0cHV0OiBgU2FtZWAuIE91dHB1dCBpcyBvZiB0aGUgc2FtZSBzaGFwZSBhcyBpbnB1dAogICAgRXhhbXBsZXM6OgogICAgICAgID4+PiBtID0gbm4uRHJvcG91dChwPTAuMikKICAgICAgICA+Pj4gaW5wdXQgPSBhdXRvZ3JhZC5WYXJpYWJsZSh0b3JjaC5yYW5kbigyMCwgMTYpKQogICAgICAgID4+PiBvdXRwdXQgPSBtKGlucHV0KQogICAgLi4gX0ltcHJvdmluZyBuZXVyYWwgbmV0d29ya3MgYnkgcHJldmVudGluZyBjby1hZGFwdGF0aW9uIG9mIGZlYXR1cmUKICAgICAgICBkZXRlY3RvcnM6IGh0dHBzOi8vYXJ4aXYub3JnL2Ficy8xMjA3LjA1ODAKICAgICIiIgoKICAgIGRlZiBfX2luaXRfXyhzZWxmLCBwPTAuNSwgZHJvcG91dE1DPVRydWUsIGlucGxhY2U9RmFsc2UpOgogICAgICAgIHN1cGVyKERyb3BvdXRNQywgc2VsZikuX19pbml0X18oKQogICAgICAgIGlmIHAgPCAwIG9yIHAgPiAxOgogICAgICAgICAgICByYWlzZSBWYWx1ZUVycm9yKCJkcm9wb3V0IHByb2JhYmlsaXR5IGhhcyB0byBiZSBiZXR3ZWVuIDAgYW5kIDEsICIKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAiYnV0IGdvdCB7fSIuZm9ybWF0KHApKQogICAgICAgIHNlbGYucCA9IHAKICAgICAgICBzZWxmLmRyb3BvdXRNQyA9IGRyb3BvdXRNQwogICAgICAgIHNlbGYuaW5wbGFjZSA9IGlucGxhY2UKCiAgICBkZWYgZm9yd2FyZChzZWxmLCBpbnB1dCk6CiAgICAgICAgcmV0dXJuIEYuZHJvcG91dChpbnB1dCwgc2VsZi5wLCBzZWxmLmRyb3BvdXRNQywgc2VsZi5pbnBsYWNlKQoKICAgIGRlZiBfX3JlcHJfXyhzZWxmKToKICAgICAgICBpbnBsYWNlX3N0ciA9ICcsIGlucGxhY2UnIGlmIHNlbGYuaW5wbGFjZSBlbHNlICcnCiAgICAgICAgcmV0dXJuIHNlbGYuX19jbGFzc19fLl9fbmFtZV9fICsgJygnIFwKICAgICAgICAgICAgKyAncD0nICsgc3RyKHNlbGYucCkgXAogICAgICAgICAgICArIGlucGxhY2Vfc3RyICsgJyknCmBgYAo8YnI+CgojIyMgSW5mZXJlbmNlCgpXZSBuZWVkIHRvIGRlZmluZSBhIGZ1bmN0aW9uIHRoYXQgcGVyZm9ybXMgaW5mZXJlbmNlIG92ZXIgb3V0IGlucHV0LiBUaGUgZm9sbG93aW5nIGNodW5rIGNvbnRhaW5zIHRoZSByZWxldmFudCBjb2RlIGZvciB0aGUgc2FtcGxpbmcgcHJvY2VkdXJlIGRlc2NyaWJlZCBpbiBzZWN0aW9uIDEuMS4gVGhlIGZ1bmN0aW9uIGBpbmZlcmVuY2VgIHN0b3JlcyBhbGwgdGhlIHJlbGV2YW50IHN0YXRpc3RpY3MgYW5kIHNvZnRtYXggZGlzdHJpYnV0aW9ucyBpbiBhIGRpY3Rpb25hcnkgbmFtZWQgYG91dHB1dGAuIFRoZSByZXN1bHRzIGFyZSB0aGVuIHR1cm5lZCBpbnRvIGEgYHBhbmRhc2AgZGF0YWZyYW1lIGFuZCBzb21lIHZlcnkgYmFzaWMgZmVhdHVyZSBlbmdpbmVlcmluZyBpcyBwZXJmb3JtZWQuIEZpbmFsbHksIHRoZSBkYXRhIGlzIHByZXBhcmVkIGZvciBzdGF0aXN0aWNhbCBhbmFseXNpcyBpbiBSLgoKYGBge3B5dGhvbiBweXRob24ucmV0aWN1bGF0ZT1GQUxTRSwgZXZhbD1GQUxTRX0KZGVmIGluZmVyZW5jZShsZWFybmVyLCBkYXRhLCBUPTEwMCk6CiAgICAnJycgRnVuY3Rpb24gdGhhdCBnYXRoZXJzIGFsbCByZWxldmFudCBudW1lcmljYWwgcmVzdWx0cyBmcm9tIE1DIGRyb3BvdXQgb3ZlciBUIGl0ZXJhdGlvbnMuCiAgICAgICAgCiAgICAgICAgQXJndW1lbnRzOgogICAgICAgIGxlYXJuZXIsIGZhc3RhaSBsZWFybmVyIG9iamVjdAogICAgICAgIGRhdGEsIGZhc3RhaSBkYXRhbG9hZGVyCiAgICAgICAgVCwgbnVtYmVyIG9mIHN0b2NoYXN0aWMgZm9yd2FyZCBwYXNzZXMKICAgICcnJwogICAgIyBHZXQgaW1hZ2VzLCBsYWJlbHMgYW5kIGZpbGVuYW1lcwogICAgaW1ncywgbGFiZWxzID0gbmV4dChpdGVyKGRhdGEudmFsX2RsKSkKICAgIGZuYW1lcyA9IGRhdGEudmFsX2RzLmZuYW1lcwoKICAgICMgRW1wdHkgZGljdGlvbmFyeSB0byBzdG9yZSBhbGwgb3V0cHV0CiAgICBvdXRwdXQgPSB7fQoKICAgICMgRW1wdHkgYXJyYXkgdG8gc3RvcmUgcmVzdWx0cyBpbgogICAgcmVzdWx0cyA9IG5wLmVtcHR5KChULCBudW1fY2xhc3NlcykpCgogICAgIyBpdGVyYXRvciBpbmRleCB0byBrZWVwIGluIGRpY3Rpb25hcnkKICAgIGs9MAoKICAgIGZvciAoaW1nLCBsYWJlbCwgZm5hbWUpIGluIGxpc3QoemlwKGltZ3MsIGxhYmVscywgZm5hbWVzKSk6CgogICAgICAgIGZvciBpIGluIHJhbmdlKFQpOgogICAgICAgICAgICBwcmVkaWN0aW9uID0gbGVhcm5lci5wcmVkaWN0X2FycmF5KGltZ1tOb25lXSkKICAgICAgICAgICAgcmVzdWx0c1tpXSA9IHByZWRpY3Rpb24KCiAgICAgICAgcHJvYnMgPSB0b19ucChGLnNvZnRtYXgoVihyZXN1bHRzKSkpCiAgICAgICAgcHJvYnNfbWVhbiA9IG5wLm1lYW4ocHJvYnMsIGF4aXM9MCkKICAgICAgICBwcmVkX3N0ZCA9IG5wLnN0ZChwcm9icywgYXhpcz0wKQoKICAgICAgICBwcmVkaWN0aW9uID0gcHJvYnNfbWVhbi5hcmdtYXgoKQogICAgICAgIHVuY2VydGFpbnR5ID0gcHJlZF9zdGRbcHJlZGljdGlvbl0KCiAgICAgICAgY29ycmVjdCA9IDEgaWYgcHJlZGljdGlvbiA9PSBsYWJlbCBlbHNlIDAKCiAgICAgICAgb3V0cHV0W2tdID0geyJpbWciOiBmbmFtZSwgInNvZnRtYXhfZGlzdCI6IHByb2JzLCAicHJvYnMiOiBwcm9ic19tZWFuLCAicHJlZGljdGlvbiI6IHByZWRpY3Rpb24sICJ0cnV0aCI6IGxhYmVsLCAidW5jZXJ0YWludHkiOiB1bmNlcnRhaW50eSwgImNvcnJlY3QiOiBjb3JyZWN0fQogICAgICAgIGsrPTEKICAgIAogICAgcmV0dXJuIG91dHB1dApgYGAKCiMjIFRyYWluaW5nCgpPdXIgbW9kZWwgd2FzIHRyYWluZWQgb24gQ0lGQVItMTAgdXNpbmcgdGhlIGBmYXN0YWlgIEFQSS4gQ0lGQVItMTAgY29udGFpbnMgNjAuMDAwIGxhYmVsbGVkIDMyeDMyeDMgY29sb3IgaW1hZ2VzIGJlbG9uZ2luZyB0byAxMCBkaWZmZXJlbnQgY2xhc3Nlcy4gVGhlIGlucHV0IGRhdGEgd2FzIHNwbGl0IGludG8gYSB0cmFpbmluZyBzZXQgb2YgNTAuMDAwIGltYWdlcyBhbmQgYSB0ZXN0IHNldCBvZiAxMC4wMDAgaW1hZ2VzLiBUaGUgdHJhaW5pbmcgc2V0IHdhcyBmdXJ0aGVyIHNwbGl0IGludG8gYSB0cmFpbmluZyBzZXQgYW5kIGEgdmFsaWRhdGlvbiBzZXQuIAoKVGhlIG5ldHdvcmsgd2FzIHRyYWluZWQgZm9yIDYwIGVwb2NocyB3aXRoIGEgbGVhcm5pbmcgcmF0ZSBvZiAkMC4wMDEkIChmb3VuZCB1c2luZyBgbHJfZmluZGAgZnVuY3Rpb25hbGl0eSBpbiBgZmFzdGFpYCksIGBrZXJuZWwgc2l6ZSA9ICg1LDUpYCwgYGRyb3BfcmF0ZSA9IC41YCBhbmQgYHdlaWdodF9kZWNheSA9IDAuMDAwNWAuIEl0IGlzIGlkZW50aWNhbCBpbiBzdHJ1Y3R1cmUgdG8gdGhlIG9uZSB1c2VkIGJ5IEdhbCBldC4gYWwuIFsxXS4gVGhlICoqdmFsaWRhdGlvbiBsb3NzKiogd2FzICoqMC43MTI4MCoqIGF0IGVuZCBvZiB0cmFpbmluZyB3aXRoIGFuICoqYWNjdXJhY3kgb2YgMC43NjEzNyoqIG9uIHRoZSB2YWxpZGF0aW9uIGRhdGEuCgojIyBEYXRhCgpUaGUgZGF0YSBjb250YWlucyB0aGUgZm9sbG93aW5nIHZhcmlhYmxlcyBhZnRlciBpdCBoYXMgYmVlbiBwcmVwYXJlZCBmb3IgYW5hbHlzaXMgaW4gUjoKCiogYGNvcnJlY3RgIChsb2dpY2FsKTogaW5kaWNhdG9yIHRoZSBpcyBgVFJVRWAgaWYgdGhlIHByZWRpY3RlZCBjbGFzcyBsYWJlbCBtYXRjaGVzIHRoZSB0cnVlIGNsYXNzIGxhYmVsLCBlbHNlIGBGQUxTRWAuCgoqIGBwcmVkaWN0aW9uYCAoaW50KTogcHJlZGljdGVkIGNsYXNzIGxhYmVsLgoKKiBgdHJ1dGhgIChpbnQpOiB0cnVlIGNsYXNzIGxhYmVsLgoKKiBgdW5jZXJ0YWludHlgIChkYmwpOiBlbXBpcmljYWwgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIHNvZnRtYXggdmFsdWVzIGZvciBwcmVkaWN0ZWQgY2xhc3MuCgoqIGBwcm9iMWAgKGRibCk6IGFyZ21heCBvZiBtZWFuIHNvZnRtYXggb3V0cHV0LCBpLmUuIG1lYW4gcHJvYmFiaWxpdHkgb2YgcHJlZGljdGVkIGNsYXNzLgoKKiBgcHJvYjJgIChkYmwpOiBtZWFuIHByb2JhYmlsaXR5IG9mIHJ1bm5lci11cCBwcmVkaWN0aW9uLgoKKiBgY2xhc3MyYCAoaW50KTogY2xhc3MgbGFiZWwgb2YgcnVubmVyLXVwIHByZWRpY3Rpb24uCgoqIGBkaWZmYCAoZGJsKTogYHByb2IxYC1gcHJvYjJgCgoqIGBkaWZmX3NkX3JhdGlvYCAoZGJsKTogYGRpZmYvdW5jZXJ0YWludHlgLgoKQWxsIHRoZSB2YXJpYWJsZXMgYWJvdmUgYXJlIHByZXR0eSBzdGFuZGFyZCwgd2l0aCB0aGUgZXhjZXB0aW9uIG9mIGBkaWZmX3NkX3JhdGlvYC4gSW50dWl0aXZlbHksIGlmIGBkaWZmYCBpcyBsYXJnZSwgdGhlIGF2ZXJhZ2VkIG1vZGVscyBhbGwgYWdyZWUgdGhhdCBjbGFzcyAkayQgaXMgdGhlIGNvcnJlY3QgcHJlZGljdGlvbi4gSWYgYGRpZmZgIGlzIHNtYWxsLCB0aGUgbW9kZWxzIHNhbXBsZWQgYnkgTUMgZHJvcG91dCBkb24ndCBhZ3JlZSBvbiBhIHNpbmdsZSBjbGFzcy4gVGh1cyBgZGlmZmAgYWxzbyBzZXJ2ZXMgYXMgYSBwcm94eSBmb3IgdW5jZXJ0YWludHkuIE1vZGVsIGB1bmNlcnRhaW50eWAsIGhvd2V2ZXIsIGlzIGFwcHJveGltYXRlZCBieSB0aGUgZW1waXJpY2FsIHN0YW5kYXJkIGRldmlhdGlvbiBvZiB0aGUgcHJlZGljdGlvbnMgZm9yIGNsYXNzICRrJC4gVGh1cyBgZGlmZl9zZF9yYXRpb2AgaXMgZXhwcmVzc2VkIGJ5ICQkXHRhdV97a2p9ID0gXGZyYWN7XGhhdHtcbXV9X2sgLSBcaGF0e1xtdX1fan17XGhhdHtcc2lnbWF9X2t9JCQgd2hlcmUgJGokIGlzIHRoZSBydW5uZXItdXAgcHJlZGljdGlvbi4gJFx0YXVfe2prfSQgZ2l2ZXMgdXMgYSByYXRpbyBvZiB0d28gZGlmZmVyZW50IG1lYXN1cmVzIG9mIHVuY2VydGFpbnR5LgoKIyBDbGFzc2lmaWNhdGlvbiBSZXN1bHRzCgpUaGUgZm9sbG93aW5nIHRhYmxlIHN1bW1hcmlzZXMgdGhlIHJlc3VsdHMgb3ZlciB0aGUgZW50aXJlIGRhdGEgc2V0OgoKYGBge3J9CiMgSW1wb3J0aW5nIGRhdGEKZGF0YSA8LSByZWFkLmNzdigifi9Eb2N1bWVudHMvTWFzdGVyb3BwZ2F2ZS9EYXRhL1Jlc3VsdGF0ZXIvbGVuZXQtbW9kZWw1NS5jc3YiKQpkZiA8LSBkcGx5cjo6c2VsZWN0KGRhdGEsIC1YKQoKIyBBZ2dyZWdhdGluZyBzdW1tYXJ5IHN0YXRpc3RpY3MgYnkgY29ycmVjdC9pbmNvcnJlY3QKcmVzdWx0cyA8LSBkZiAlPiUKICBzdW1tYXJpc2Uobj1uKCksCiAgICAgICAgICAgIGFjY3VyYWN5ID0gc3VtKGNvcnJlY3Q9PTEpL24sCiAgICAgICAgICAgIG1lYW5fcHJvYjE9bWVhbihwcm9iMSksCiAgICAgICAgICAgIG1lYW5fcHJvYjI9bWVhbihwcm9iMiksCiAgICAgICAgICBtZWFuX3VuY2VydGFpbnR5PW1lYW4odW5jZXJ0YWludHkpLAogICAgICAgICAgbWVkaWFuX3VuY2VydGFpbnR5PW1lZGlhbih1bmNlcnRhaW50eSksCiAgICAgICAgICBzZF91bmNlcnRhaW50eT1zZCh1bmNlcnRhaW50eSksIAogICAgICAgICAgbWVhbl9kaWZmPW1lYW4oZGlmZiksCiAgICAgICAgICBtZWRpYW5fZGlmZj1tZWRpYW4oZGlmZiksCiAgICAgICAgICBzZF9kaWZmPXNkKGRpZmYpLAogICAgICAgICAgbWVhbl9yYXRpbz1tZWFuKGRpZmZfc2RfcmF0aW8pLAogICAgICAgICAgbWVkaWFuX3JhdGlvPW1lZGlhbihkaWZmX3NkX3JhdGlvKSwKICAgICAgICAgIHNkX3JhdGlvPXNkKGRpZmZfc2RfcmF0aW8pKQpyZXN1bHRzCmBgYApUaGUgbmV4dCB0YWJsZSBzaG93cyB0aGUgc3VtbWFyeSBzdGF0aXN0aWNzIGFmdGVyIHBhcnRpdGlvbmluZyB0aGUgZGF0YSBieSBpbmNvcnJlY3QvY29ycmVjdCBjbGFzc2lmaWNhdGlvbnM6CmBgYHtyfQojIEFnZ3JlZ2F0aW5nIHN1bW1hcnkgc3RhdGlzdGljcyBieSBjb3JyZWN0L2luY29ycmVjdAphZ2dfZGYgPC0gZGYgJT4lIAogIGdyb3VwX2J5KGNvcnJlY3QpICU+JSAKICBzdW1tYXJpc2Uobj1uKCksCiAgICAgICAgICAgIGFjY3VyYWN5PW4vMTAwMDAsCiAgICAgICAgICAgIG1lYW5fcHJvYjE9bWVhbihwcm9iMSksCiAgICAgICAgICAgIG1lYW5fcHJvYjI9bWVhbihwcm9iMiksCiAgICAgICAgICBtZWFuX3VuY2VydGFpbnR5PW1lYW4odW5jZXJ0YWludHkpLAogICAgICAgICAgbWVkaWFuX3VuY2VydGFpbnR5PW1lZGlhbih1bmNlcnRhaW50eSksCiAgICAgICAgICBzZF91bmNlcnRhaW50eT1zZCh1bmNlcnRhaW50eSksIAogICAgICAgICAgbWVhbl9kaWZmPW1lYW4oZGlmZiksCiAgICAgICAgICBtZWRpYW5fZGlmZj1tZWRpYW4oZGlmZiksCiAgICAgICAgICBzZF9kaWZmPXNkKGRpZmYpLAogICAgICAgICAgbWVhbl9yYXRpbz1tZWFuKGRpZmZfc2RfcmF0aW8pLAogICAgICAgICAgbWVkaWFuX3JhdGlvPW1lZGlhbihkaWZmX3NkX3JhdGlvKSwKICAgICAgICAgIHNkX3JhdGlvPXNkKGRpZmZfc2RfcmF0aW8pKQphZ2dfZGYKYGBgCgpPdmVyYWxsIG91ciBtb2RlbCBjbGFzc2lmaWVzIGByIGFnZ19kZiRuWzJdYCBpbWFnZXMgY29ycmVjdGx5IG91dCBvZiAkTj0xMC4wMDAkLCBnaXZpbmcgaXQgYW4gYWNjdXJhY3kgb2YgYHIgKGFnZ19kZiRuWzJdLzEwMDAwKSoxMDBgJS4gSW4gYnJpZWYsIHRoZSBzdW1tYXJ5IHN0YXRpc3RpY3MgaW5kaWNhdGUgdGhhdCBzb2Z0bWF4IG91dHB1dHMgb2YgdGhlIHByZWRpY3RlZCBhbmQgcnVubmVyLXVwIGNsYXNzZXMgc2VlbSB0byBiZSBjbG9zZXIgdG8gZWFjaCBvdGhlciB3aGVuIHRoZSBtb2RlbCBtaXNjbGFzc2lmaWVzLiBGdXJ0aGVybW9yZSwgaW5jb3JyZWN0bHkgY2xhc3NpZmllZCBpbWFnZXMgc2VlbSB0byBiZSBhc3NvY2lhdGVkIHdpdGggZ3JlYXRlciB1bmNlcnRhaW50eSBvbiBhdmVyYWdlLiBUaGlzIHJlc3VsdCBpcyBvZiBjcnVjaWFsIGltcG9ydGFuY2UgYW5kIGlzIGEgbmVjZXNzYXJ5IGNvbmRpdGlvbiBmb3IgZXhwbG9yaW5nIGhvdyB1bmNlcnRhaW50eSBhcHByb3hpbWF0aW9uIGNvcnJlbGF0ZXMgd2l0aCBtb2RlbCBwcmVkaWN0aW9ucy4KClRoZSBtb2RlbCBpcyBtb3N0IHN1Y2Nlc3NmdWwgd2hlbiBjbGFzc2lmeWluZyBpbWFnZXMgb2YgYXV0b21vYmlsZXMgKDkwMiBjb3JyZWN0KSBhbmQgZnJvZ3MgKDg5MSBjb3JyZWN0KS4gVGhlIGxlYXN0IHN1Y2Nlc3NmdWwgcHJlZGljdGlvbnMgb2NjdXIgaW4gdGhlIGNhdCBjYXRlZ29yeSwgd2l0aCA1NjUgY29ycmVjdCBjbGFzc2lmaWNhdGlvbnMuIFRoaXMgaXMgc3VtbWFyaXplZCBpbiB0aGUgZm9sbG93aW5nIGNvbmZ1c2lvbiBtYXRyaXg6CgohW10oRmlndXJlcy9jb25mX21hdF9kYXQyNTkuanBnKQoKVGhlIGNvbmZ1c2lvbiBtYXRyaXggYWJvdmUgcHJvdmlkZXMgZGV0YWlscyBvZiBleGFjdGx5IGhvdyB0aGUgbW9kZWwgZmFpbHMuIEluIGltYWdlcyBvZiBjYXRzIHRoZSBtb3N0IGZyZXF1ZW50IG1pc2NsYXNzaWZpY2F0aW9uIGlzIGRvZyAoMTQ1KS4gRm9yIGRvZ3MgdGhlIG1vc3QgZnJlcXVlbnQgaW5jb3JyZWN0IGxhYmVsIGlzIGNhdCAoMTM1KS4gSW4gZ2VuZXJhbCBpdCBzZWVtcyB0aGF0IHRoZSBtaXNjbGFzc2lmaWNhdGlvbnMsIGFsdGhvdWdoIHdyb25nLCBiZWxvbmcgdG8gdGhlIHNhbWUgZG9tYWluIGFzIHRoZSBjb3JyZWN0IGxhYmVsIChpLmUuIG9uZSB2ZWhpY2xlIHR5cGUgaXMgbWlzdGFrZW4gZm9yIGFub3RoZXIgYW5kIG9uZSBzcGVjaWVzIG9mIGFuaW1hbCBpcyBtaXNjbGFzc2lmaWVkIGFzIGFub3RoZXIpLiBUaGlzIHN1Z2dlc3RzIHRoYXQgb3VyIG1vZGVsIGlzIHVuYWJsZSB0byBsZWFybiBkaXN0aW5ndWlzaGluZyBmZWF0dXJlcyB3aGljaCBhZGVxdWF0ZWx5IHNlcGVyYXRlIHNpbWlsYXIgY2xhc3Nlcy4gSG93ZXZlciwgb25lIHNob3VsZCBjYXV0aW91cyBhYm91dCByZWFkaW5nIHRvbyBtdWNoIGludG8gdGhlIHR5cGUgb2YgZXJyb3JzIGJlaW5nIG1hZGUuIFRoZSByZXN1bHRzIG1heSB2ZXJ5IHdlbGwgYmUgYW4gYXJ0ZWZhY3Qgb2YgdGhlIG1vZGVsLCB0aGUgZGF0YSBzZXQgb3IgYm90aC4KCiMjIEV4YW1wbGVzIG9mIFVuY2VydGFpbiBDbGFzc2lmaWNhdGlvbnMgey50YWJzZXR9CgpJbiB0aGUgZm9sbG93aW5nIHdlIHdpbGwgdmlzdWFsaXplIHRoZSByZWxhdGlvbnNoaXBzIGJldHdlZW4gb3VyIHZhcmlhYmxlcy4gV2Ugc3RhcnQgYnkgbG9va2luZyBhdCBleGFtcGxlcyBvZiBjZXJ0YWluIGFuZCB1bmNlcnRhaW4gaW1hZ2VzLiBUaGUgd2UgZXhhbWluZSB0aGUgZW1waXJpY2FsIGRpc3RyaWJ1dGlvbiBvZiB0aGUgdW5jZXJ0YWludHkgZXN0aW1hdGVzICRcaGF0e1xzaWdtYX1fayQuCgojIyMgSW5jb3JyZWN0IGNsYXNzaWZpY2F0aW9ucwoKVGhlIGZvbGxvd2luZyBwbG90cyB3ZXJlIGdlbmVyYXRlZCB1c2luZyBQeXRob24gKGNvZGUgYXZhaWxhYmxlIG9uIFtHaXRIdWJdKGxpbmspKS4gT24gdGhlIGxlZnQgaGFuZCBzaWRlIHdlIHNlZSB0aGUgdW5ub3JtYWxpemVkIGltYWdlIHdpdGggdGhlIGNvcnJlc3BvbmRpbmcgZ3JvdW5kIHRydXRoIGxhYmVsLiBUaGUgcGxvdCBpbiB0aGUgbWlkZGxlIHNob3dzIHRoZSBzb2Z0bWF4IG91dHB1dCBvZiB0aGUgcHJlZGljdGVkIGNsYXNzIGZvciBlYWNoIG9mIHRoZSAkVD0xMDAkIHN0b2NoYXN0aWMgZm9yd2FyZCBwYXNzZXMuICRcbXVfayQgaXMgZ2l2ZW4gYnkgdGhlIHNvbGlkIHJlZCBsaW5lLCAkXG11X2okIGlzIGdpdmVuIGJ5IHRoZSBkYXNoZWQgYnJvd24gbGluZS4gVGhlIHBsb3QgdGl0bGUgc2hvd3MgYm90aCB0aGUgcHJlZGljdGVkIGNsYXNzIGFuZCB0aGUgcnVubmVyLXVwIGNsYXNzLiBUbyB0aGUgcmlnaHQgaXMgYSBrZXJuZWwgZGVuc2l0eSBlc3RpbWF0ZSAodXNpbmcgYSBHYXVzc2lhbiBrZXJuZWwpIG9mIHRoZSAkVD0xMDAkIHNvZnRtYXggb3V0cHV0cyBmb3IgdGhlIHByZWRpY3RlZCBjbGFzcy4gVGhlIHBsb3RzIHNob3cgdGhlIHRvcCA1IG1vc3QgdW5jZXJ0YWluIGNsYXNzaWZpY2F0aW9ucyBpbiB0aGUgZW50aXJlIGRhdGEgc2V0LgoKIVtdKEZpZ3VyZXMvODYwMS5qcGVnKQohW10oRmlndXJlcy81MzAyLmpwZWcpCiFbXShGaWd1cmVzLzQzNDAuanBlZykKIVtdKEZpZ3VyZXMvNTU3Mi5qcGVnKQohW10oRmlndXJlcy8xMjQ4LmpwZWcpCgojIyMgQ29ycmVjdCBjbGFzc2lmaWNhdGlvbnMKCiFbXShGaWd1cmVzLzI1NzkuanBlZykKIVtdKEZpZ3VyZXMvOTQ2OC5qcGVnKQohW10oRmlndXJlcy84MTY5LmpwZWcpCiFbXShGaWd1cmVzLzc3NzguanBlZykKIVtdKEZpZ3VyZXMvMTA3OS5qcGVnKQoKVGhlIHJ1bm5lci11cCBwcmVkaWN0aW9uIGZvciB0aGUgZml2ZSBtb3N0IHVuY2VydGFpbiBidXQgY29ycmVjdCBwcmVkaWN0aW9ucyBhcmUgYWxsICJhaXJwbGFuZSIuIE9uZSBwb3NzaWJsZSBleHBsYW5hdGlvbiBpcyB0aGUgcHJlc2VuY2Ugb2YgbGFyZ2UgYXJlYXMgb2YgYmx1ZSBhbmQvb3Igd2hpdGUsIHdoaWNoIHdlIG1pZ2h0IGFzc3VtZSB3b3VsZCBiZSBwcmVzZW50IGFzIGJhY2tncm91bmRzIGluIGltYWdlcyBvZiBwbGFuZXMgZmx5aW5nIHRocm91Z2ggdGhlIHNreS4KCiMjIERpc3RyaWJ1dGlvbiBvZiBVbmNlcnRhaW50eQoKVGhlIGRpc3RyaWJ1dGlvbiBvZiB0b3RhbCB1bmNlcnRhaW50eSBhcHBlYXJzIHRvIGJlIGJpbW9kYWwsIHdpdGggcGVha3MgY2xvc2UgdG8gMCBhbmQgMC4yOgoKYGBge3IgZmlnLmhlaWdodD00LCBmaWcud2lkdGg9Nn0KIyBEaXN0cmlidXRpb24gb2YgZXN0aW1hdGVkIHVuY2VydGFpbnR5CnAxIDwtIGRmICU+JSAKICBnZ3Bsb3QoYWVzKHg9dW5jZXJ0YWludHkpKSArCiAgZ2VvbV9oaXN0b2dyYW0oY29sPSJncmV5IiwgYmlucyA9IDUwLCBhbHBoYT0uNSkgKwogIGdndGl0bGUoIkRpc3RyaWJ1dGlvbiBvZiBlc3RpbWF0ZWQgdW5jZXJ0YWludHkiKSArCiAgdGhlbWVfYncoKQpwMQpgYGAKCkJ5IGdyb3VwaW5nIHRoZSB1bmNlcnRhaW50eSBlc3RpbWF0ZXMgYnkgYGNvcnJlY3RgIChpLmUuIGlmIHRoZSBsYWJlbCB3YXMgY29ycmVjdGx5IHByZWRpY3RlZCBvciBub3QpLCB3ZSBjYW4gZmluZCBvdXQgaG93IHRoZSBwcmVkaWN0aW9ucyBjb250cmlidXRlIHRvIHRoZSB1bmNlcnRhaW50eSBkaXN0cmlidXRpb246CgpgYGB7cn0KI0Rpc3RyaWJ1dGlvbiBvZiBlc3RpbWF0ZWQgdW5jZXJ0YWludHkgYnkgcHJlZGljdGlvbgpwMiA8LSBkZiAlPiUgCiAgZ2dwbG90KGFlcyh4PXVuY2VydGFpbnR5LCBjb2w9YXMuZmFjdG9yKGNvcnJlY3QpKSkgKwogIGdlb21fZnJlcXBvbHkoYWxwaGE9LjcpICsKICBnZ3RpdGxlKCJEaXN0cmlidXRpb24gb2YgZXN0aW1hdGVkIHVuY2VydGFpbnR5IGJ5IGNsYXNzaWZpY2F0aW9uIikgKwogIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKG5hbWU9IlByZWRpY3Rpb24iLAogICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWtzPWMoIjAiLCAiMSIpLAogICAgICAgICAgICAgICAgICAgICAgICAgbGFiZWxzPWMoIjA6IEluY29ycmVjdCIsICIxOiBDb3JyZWN0IikpICsKICB0aGVtZV9idygpCnAyCmBgYApUaGUgYmx1ZSBsaW5lIGNvcnJlc3BvbmRzIHRvIHRoZSBjb3JyZWN0IHByZWRpY3Rpb25zLCB0aGUgcmVkIGxpbmUgY29ycmVzcG9uZHMgdG8gaW5jb3JyZWN0IHByZWRpY3Rpb25zLiBXZSBzZWUgdGhhdCB0aGUgaW5jb3JyZWN0IHByZWRpY3Rpb25zIGFyZSBjZW50ZXJlZCBhcm91bmQgYSBoaWdoZXIgYXNzb2NpYXRlZCB1bmNlcnRhaW50eSwgd2hlcmVhcyBmYXIgbW9yZSBvZiB0aGUgY29ycmVjdGx5IHByZWRpY3RlZCBjbGFzc2VzIGFyZSBjb25jZW50cmF0ZWQgYXJvdW5kIGEgbG93IHVuY2VydGFpbnR5IHZhbHVlLiBUaGUgaW5jb3JyZWN0IGNsYXNzaWZpY2F0aW9ucyBncmVhdGx5IGNvbnRyaWJ1dGUgdG8gdGhlIGJpbW9kYWxpdHksIGJ1dCBpdCBpcyBhbHNvIHByZXNlbnQgaW4gdGhlIGRpc3RyaWJ1dGlvbiBvZiB1bmNlcnRhaW50eSBmb3IgdGhlIGNvcnJlY3QgY2xhc3NpZmljYXRpb25zLiAKClRoZSBmb2xsb3dpbmcgZGVuc2l0eSBwbG90cyBnaXZlcyB1cyBhbiBpZGVhIG9mIGhvdyB0aGUgZGlzdHJpYnV0aW9ucyBjb21wYXJlIHRvIGVhY2hvdGhlcjoKCmBgYHtyfQojIEtERSBieSBjb3JyZWN0IHByZWRpY3Rpb24KbGluZXNfZGYgPC0gZGYgJT4lIAogIGdyb3VwX2J5KGNvcnJlY3QpICU+JSAKICBzdW1tYXJpc2UobWVhbl91bmNlcnRhaW50eT1tZWFuKHVuY2VydGFpbnR5KSkKCnAzIDwtIGRmICU+JSAKICBnZ3Bsb3QoYWVzKHg9dW5jZXJ0YWludHksIGdyb3VwPWZhY3Rvcihjb3JyZWN0KSkpICsKICBnZW9tX2hpc3RvZ3JhbShhZXMoeT0uLmRlbnNpdHkuLiwgZmlsbD1mYWN0b3IoY29ycmVjdCkpLCBwb3NpdGlvbj0iaWRlbnRpdHkiLCBiaW5zID0gNTAsIGFscGhhPS41KSArCiAgZ2VvbV9kZW5zaXR5KGFlcyh5PS4uZGVuc2l0eS4uLCBjb2w9ZmFjdG9yKGNvcnJlY3QpKSwgYWxwaGE9LjUpICsKICBnZW9tX3J1ZyhhZXMoeD11bmNlcnRhaW50eSwgY29sPWZhY3Rvcihjb3JyZWN0KSksIGFscGhhPS41KSArCiAgZ2VvbV92bGluZShkYXRhID0gbGluZXNfZGYsIGFlcyh4aW50ZXJjZXB0PW1lYW5fdW5jZXJ0YWludHksIGNvbD1mYWN0b3IoY29ycmVjdCkpLCBsdHk9ImRhc2hlZCIpICsKICBnZ3RpdGxlKCJEaXN0cmlidXRpb25zIG9mIHVuY2VydGFpbnR5IGJ5IGNsYXNzaWZpY2F0aW9uIikgKwogIGxhYnMoY29sb3I9IlByZWRpY3Rpb24iLAogICAgICAgZmlsbD0iUHJlZGljdGlvbiIpICsKICBzY2FsZV9jb2xvcl9kaXNjcmV0ZShicmVha3M9YygiMCIsICIxIiksCiAgICAgICAgICAgICAgICAgICAgICAgICBsYWJlbHM9YygiMDogSW5jb3JyZWN0IiwgIjE6IENvcnJlY3QiKSkgKwogIHNjYWxlX2ZpbGxfZGlzY3JldGUoYnJlYWtzPWMoIjAiLCAiMSIpLAogICAgICAgICAgICAgICAgICAgICAgICAgbGFiZWxzPWMoIjA6IEluY29ycmVjdCIsICIxOiBDb3JyZWN0IikpICsKICB0aGVtZV9idygpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSBjKC45LC44NSkpCnAzCmBgYAoKVGhlIGJveHBsb3QgZ2l2ZXMgdXMgeWV0IGFub3RoZXIgd2F5IHRvIHZpc3VhbGl6ZSB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHVuY2VydGFpbnR5IGRpc3RyaWJ1dGlvbnMgYnkgcHJlZGljdGl2ZSBhYmlsaXR5OgoKYGBge3J9CiMgQm94cGxvdCBvZiB1bmNlcnRhaW50aWVzIGZvciBjb3JyZWN0IHZzLiBpbmNvcnJlY3QKcDQgPC0gZGYgJT4lIAogIGdncGxvdChhZXMoeD1hcy5mYWN0b3IoY29ycmVjdCksIHk9dW5jZXJ0YWludHkpKSArCiAgZ2VvbV9ib3hwbG90KGFlcyhmaWxsPWFzLmZhY3Rvcihjb3JyZWN0KSksIGFscGhhPS43KSArCiAgbGFicyh4PSJjb3JyZWN0IikgKwogIGdndGl0bGUoIkJveHBsb3Qgb2YgdW5jZXJ0YWludHkgZGlzdHJpYnV0aW9uIGJ5IGNvcnJlY3QvaW5jb3JyZWN0IikgKwogIHNjYWxlX2ZpbGxfZGlzY3JldGUobmFtZT0iUHJlZGljdGlvbiIsCiAgICAgICAgICAgICAgICAgICAgICAgICBicmVha3M9YygiMCIsICIxIiksCiAgICAgICAgICAgICAgICAgICAgICAgICBsYWJlbHM9YygiMDogSW5jb3JyZWN0IiwgIjE6IENvcnJlY3QiKSkgKyAKICB0aGVtZV9idygpCnA0CmBgYAoKSWYgJFxoYXR7XHNpZ21hfV9rJCBpcyBhIHVzZWZ1bCBhcHByb3hpbWF0aW9uIG9mIG1vZGVsIHVuY2VydGFpbnR5LCB0aGVuIHdlIHdvdWxkIGV4cGVjdCB0aGUgZGlzdHJpYnV0aW9ucyAkXGhhdHtcc2lnbWF9X2skIGZvciBjb3JyZWN0bHkgYW5kIGluY29ycmVjdGx5IGNsYXNzaWZpZWQgaW1hZ2VzIHRvIHJlZmxlY3QgdGhpcyBzb21laG93LiBGcm9tIHRoZSBmaWd1cmVzIGFib3ZlLCBpdCBzZWVtcyBjbGVhciB0aGF0IHRoZSBkaXN0cmlidXRpb25zIG9mIHVuY2VydGFpbnRpZXMgYXJlIG1lYW5pbmdmdWxseSBkaWZmZXJlbnQgZnJvbSBvbmUgYW5vdGhlciwgYXQgbGVhc3QgZm9yIHRoaXMgcGFydGljdWxhciBjaG9pY2Ugb2YgbW9kZWwgYW5kIGRhdGEgc2V0LiBUaGlzIGluZGljYXRlcyB0aGF0IHRoZSB1bmNlcnRhaW50eSBhcHByb3hpbWF0aW9uIGl0c2VsZiBtYXkgY29udGFpbiB2YWx1ZWFibGUgaW5mb3JtYXRpb24gYWJvdXQgdGhlIG1vZGVsJ3MgY29uZmlkZW5jZSBpbiBpdHMgb3duIHByZWRpY3Rpb25zLgoKIyMgQ2xhc3Mtc3BlY2lmaWMgdW5jZXJ0YWludHkKCklmICRcaGF0e1xzaWdtYX1fayQgY2FwdHVyZXMgbW9kZWwgdW5jZXJ0YWludHksIHRoZW4gd2Ugd291bGQgZXhwZWN0IHRoZSBjbGFzcy1zcGVjaWZpYyBkaXN0cmlidXRpb25zIG9mICRcaGF0e1xzaWdtYX1fayQgdG8gc29tZWhvdyBlY2hvIHRoZSBjb25mdXNpb24gbWF0cml4IGluIHNlY3Rpb24gMy4gTGV0ICRcaGF0e1xzaWdtYX1faiQgZGVub3RlIHRoZSBjbGFzcy1zcGVjaWZpYyB1bmNlcnRhaW50eSwgd2hlcmUgJGogXGluIFx7XHRleHR7YWlycGxhbmV9LC4uLixcdGV4dHt0cnVja31cfSQgaXMgdGhlIGNvcnJlc3BvbmRpbmcgY2xhc3MgbGFiZWwuCgpgYGB7cn0KdG9fc3RyaW5nIDwtIGFzX2xhYmVsbGVyKGMoCiAgIjAiID0gImFpcnBsYW5lIiwgCiAgIjEiID0gImF1dG9tb2JpbGUiLCAKICAiMiIgPSAiYmlyZCIsCiAgIjMiID0gImNhdCIsIAogICI0IiA9ICJkZWVyIiwgCiAgIjUiID0gImRvZyIsIAogICI2IiA9ICJmcm9nIiwgCiAgIjciID0gImhvcnNlIiwgCiAgIjgiID0gInNoaXAiLCAKICAiOSIgPSAidHJ1Y2siKSkKCnVuY19kZiA8LSBkZiAlPiUgCiAgZ3JvdXBfYnkodHJ1dGgpICU+JSAKICBzdW1tYXJpc2UobWVhbl91bmNlcnRhaW50eSA9IG1lYW4odW5jZXJ0YWludHkpKQoKbWVhbl9kZiA8LSBhcy50aWJibGUocmVwKG1lYW4oZGYkdW5jZXJ0YWludHkpLCAxMCkpCgpoaXN0X2NsYXNzIDwtIGRmICU+JSAKICBnZ3Bsb3QoYWVzKHg9dW5jZXJ0YWludHkpKSArCiAgZ2VvbV9oaXN0b2dyYW0oYWVzKHk9Li5kZW5zaXR5Li4sIGZpbGw9ZmFjdG9yKHRydXRoKSksIGFscGhhPS43LCBiaW5zPTUwKSArCiAgZ2VvbV92bGluZShkYXRhPXVuY19kZiwgYWVzKHhpbnRlcmNlcHQgPSBtZWFuX3VuY2VydGFpbnR5LCBjb2w9ZmFjdG9yKHRydXRoKSksIGx3ZD0uNSwgbHR5PSJkYXNoZWQiKSArCiAgZ2VvbV92bGluZShkYXRhPW1lYW5fZGYsIGFlcyh4aW50ZXJjZXB0ID0gdmFsdWUpLCBsd2Q9LjMsIGx0eT0iZG90dGVkIikgKwogIGZhY2V0X3dyYXAofnRydXRoLCBucm93ID0gMiwgbmNvbCA9IDUsIGRyb3A9RkFMU0UsIGxhYmVsbGVyID0gdG9fc3RyaW5nKSArCiAgdGhlbWVfYncoKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKSArCiAgZ2d0aXRsZSgiRGlzdHJpYnV0aW9ucyBvZiBjbGFzcyB1bmNlcnRhaW50eSIpCgpoaXN0X2NsYXNzCmBgYAoKQXMgbm90ZWQgaW4gc2VjdGlvbiAzLCB0aGUgbW9kZWwgY2xlYXJseSBtaXN0YWtlcyBzb21lIGNhdHMgZm9yIGRvZ3MgYW5kIHNvbWUgZG9ncyBmb3IgY2F0cy4gVGhlIGNvbmZ1c2lvbiBzZWVtcyB0byBiZSByZWZsZWN0ZWQgaW4gdGhlIHJlbGF0aXZlIGRpc3RyaWJ1dGlvbnMgb2YgJFxoYXR7XHNpZ21hfV97Y2F0fSQgYW5kICRcaGF0e1xzaWdtYX1fe2RvZ30kLiAKClRoZSBmb2xsb3dpbmcgYm94cGxvdHMgZ2l2ZSBhbiBpZGVhIG9mIHRoZSBzcHJlYWQgb2YgJFxoYXR7XHNpZ21hfV9qJCBmb3IgZWFjaCBjbGFzcyAkaiQgYWZ0ZXIgZ3JvdXBpbmcgYnkgY2xhc3NpZmljYXRpb24gc3RhdHVzOgoKYGBge3J9CnRvX3N0cmluZyA8LSBhc19sYWJlbGxlcihjKAogICIwIiA9ICJhaXJwbGFuZSIsIAogICIxIiA9ICJhdXRvbW9iaWxlIiwgCiAgIjIiID0gImJpcmQiLAogICIzIiA9ICJjYXQiLCAKICAiNCIgPSAiZGVlciIsIAogICI1IiA9ICJkb2ciLCAKICAiNiIgPSAiZnJvZyIsIAogICI3IiA9ICJob3JzZSIsIAogICI4IiA9ICJzaGlwIiwgCiAgIjkiID0gInRydWNrIikpCgp1bmNfZGYgPC0gZGYgJT4lIAogIGdyb3VwX2J5KHRydXRoKSAlPiUgCiAgc3VtbWFyaXNlKG1lYW5fdW5jZXJ0YWludHkgPSBtZWFuKHVuY2VydGFpbnR5KSkKCmJveF9jbGFzcyA8LSBkZiAlPiUgCiAgZ2dwbG90KGFlcyh5PXVuY2VydGFpbnR5KSkgKwogIGdlb21fYm94cGxvdChhZXMoeD1mYWN0b3IoY29ycmVjdCksIGZpbGw9ZmFjdG9yKGNvcnJlY3QpKSwgYWxwaGE9LjcpICsKICBmYWNldF93cmFwKH50cnV0aCwgbnJvdz0yLCBuY29sPTUsIGxhYmVsbGVyID0gdG9fc3RyaW5nKSArCiAgdGhlbWVfYncoKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKSArCiAgZ2d0aXRsZSgiQm94cGxvdHMgb2YgY2xhc3MgdW5jZXJ0YWludHkiKSArCiAgbGFicyh4PSJjb3JyZWN0IikKCmJveF9jbGFzcwpgYGAKCkluIHN1bW1hcnksIHRoZSBjbGFzcy1zcGVjaWZpYyBhcHByb3hpbWF0aW9ucyBvZiB1bmNlcnRhaW50eSBpcyBjb25zaXN0ZW50IHdpdGggdGhlIGNvbmZ1c2lvbiBtYXRyaXggaW4gc2VjdGlvbiAzOiBIaWdoZXIgdW5jZXJ0YWludHkgc2VlbXMgdG8gYmUgYXNzb2NpYXRlZCB3aXRoIGNhdGVnb3JpZXMgdGhhdCB0ZW5kIHRvIGJlIG1pc2xhYmVsZWQuCgojIyBSZWxhdGlvbnNoaXAgdG8gb3RoZXIgdmFyaWFibGVzCgpBcyAkXGhhdHtcbXV9X2skIGRlY3JlYXNlcywgdGhlIHNvZnRtYXggcHJvYmFiaWxpdGllcyBhcmUgc3ByZWFkIG91dCBhY3Jvc3MgdGhlIGVsZW1lbnRzIG9mIHRoZSBwcmVkaWN0aXZlIG1lYW4gdmVjdG9yICRcaGF0e1xtdX0kLiBBbm90aGVyIHZpZXcgaXMgdGhhdCB0aGUgbnVtYmVyIG9mIGNhbmRpZGF0ZSBjbGFzc2VzIGluY3JlYXNlcy4gTmFpdmVseSwgd2Ugd291bGQgdGhlcmVmb3JlIGV4cGVjdCBsb3dlciB2YWx1ZXMgb2YgJFxoYXR7XG11fV9rJCB0byBiZSBhc3NvY2lhdGVkIHdpdGggaGlnaGVyIHVuY2VydGFpbnR5LiAKClRoZSBmb2xsb3dpbmcgZmlndXJlIHNob3dzIHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiAkXGhhdHtcc2lnbWF9X2skIGFuZCAkXGhhdHtcbXV9X2skICh3ZSBoYXZlIHBsb3R0ZWQgYSBzbW9vdGhlZCBlc3RpbWF0ZSBvZiB0aGUgbWVhbiB1bmNlcnRhaW50eSBhcyBhIGZ1bmN0aW9uIG9mIHRoZSBgcHJvYjFgIG91dHB1dCB0byBtYWtlIHRoaXMgY2xlYXJlcik6IAoKYGBge3J9CiMgUGxvdHRpbmcgc29mdG1heCBvdXRwdXQgb2YgcHJlZGljdGlvbiBhZ2FpbnN0IGVzdGltYXRlZCB1bmNlcnRhaW50eQpwNSA8LSBkZiAlPiUgCiAgZ2dwbG90KGFlcyh4PXByb2IxLCB5PXVuY2VydGFpbnR5KSkgKwogIGdlb21fcG9pbnQoYWxwaGE9LjIpICsKICBnZW9tX3Ntb290aCgpICsKICBnZ3RpdGxlKCJVbmNlcnRhaW50eSB2cy4gc29mdG1heCBwcmVkaWN0aW9uIikgKwogIGxhYnMoeD0ic29mdG1heCBvdXRwdXQgb2YgcHJlZGljdGVkIGNsYXNzIikgKwogIHRoZW1lX2J3KCkKcDUKYGBgCgpUaGUgcGxvdCBpbmRpY2F0ZXMgYSBjb25jYXZlIHNoYXBlLCB3aGljaCBjb250cmFkaWN0cyBvdXIgbmFpdmUgYXNzdW1wdGlvbi4gQSBwb3NzaWJsZSBleHBsYW5hdGlvbiBpcyB0aGF0IHRoZSBtaW5pbXVtIHZhbHVlIG9mICRcaGF0e1xtdX1fayQgaXMgYm91bmRlZCBiZWxvdyBieSAkMC4xJC4gQXMgJFxoYXR7XG11fV9rIFxyaWdodGFycm93IDAuMSQsIGFsbCB0aGUgb3RoZXIgZWxlbWVudHMgb2YgdGhlIHByZWRpY3RpdmUgbWVhbiB2ZWN0b3IgJFxoYXR7XG11fV9qIFxyaWdodGFycm93IDAuMSQuIFRoaXMgZm9sbG93cyBmcm9tIHRoZSBmYWN0IHRoYXQgJFxoYXR7XG11fV9rID0gXHRleHR7YXJnbWF4fV9rIFxoYXR7XG11fSQuIFB1cnN1aW5nIHRoaXMgbGluZSBvZiB0aG91Z2h0LCB3ZSBzcGVjdWxhdGUgdGhhdCB0aGUgbW9kZWwgbW9zdCBsaWtlbHkgeWllbGRzIHNpbWlsYXIgY2xhc3NpZmljYXRpb24gcmVzdWx0cyBmb3IgZWFjaCBzdG9jaGFzdGljIGZvcndhcmQgcGFzcyB3aGVuICRcaGF0e1xtdX1fayQgaXMgbG93LCB3aGljaCBjb25zZXF1ZW50bHkgbGVhZHMgdG8gYSBsb3dlciBlc3RpbWF0ZSBvZiAkXGhhdHtcc2lnbWF9X2skIHRodXMgZXhwbGFpbmluZyB3aHkgJFxoYXR7XHNpZ21hfV9rJCBkZWNyZWFzZXMuIFRoaXMgaGlnaGxpZ2h0cyBhIHBvdGVudGlhbCBkcmF3YmFjayBvZiB0aGUgYWQgaG9jIGFwcHJveGltYXRpb24gZ2l2ZW4gaW4gc2VjdGlvbiAxLjEgOiBBIGNsYXNzaWZpY2F0aW9uIHRoYXQgcmVzdWx0cyBpbiBtYXhpbXVtIHVuY2VydGFpbnR5IHdpdGggcmVzcGVjdCB0byBhIG1lYXN1cmUgc3VjaCBhcyBlbnRyb3B5IChpLmUuIHdoZW4gJFxoYXR7XG11fV9qID0gMC4xJCBmb3IgYWxsICRqJCkgY291bGQgcG90ZW50aWFsbHkgYmUgYXNzb2NpYXRlZCB3aXRoIGEgc21hbGwgZW1waXJpY2FsIHN0YW5kYXJkIGRldmlhdGlvbiAkXGhhdHtcc2lnbWF9X2skLgoKRnVydGhlcm1vcmUsICRcaGF0e1xzaWdtYX1fayQgc2VlbXMgdG8gcGVhayBhcm91bmQgYHByb2IxYCAkXGFwcHJveCAwLjUkLiBBZGRpdGlvbmFsIGluZm9ybWF0aW9uIGNhbiBiZSBsZXZlcmFnZWQgYnkgY29sb3VyLWNvZGluZyB0aGUgZGF0YSBwb2ludHMgYmFzZWQgb24gdGhlIHZhbHVlIG9mIHRoZSBydW5uZXItdXAgcHJlZGljdGlvbiBgcHJvYjJgLCBhcyBzaG93biBpbiB0aGUgZm9sbG93aW5nIGZpZ3VyZToKCmBgYHtyfQojIFBsb3R0aW5nIHNvZnRtYXggb3V0cHV0IG9mIHByZWRpY3Rpb24gYWdhaW5zdCBlc3RpbWF0ZWQgdW5jZXJ0YWludHksIGNvbG91cmVkIGJ5IHNvZnRtYXggb3V0cHV0IG9mIHJ1bm5lci11cApwNyA8LSBkZiAlPiUgCiAgZ2dwbG90KGFlcyh4PXByb2IxLCB5PXVuY2VydGFpbnR5KSkgKwogIGdlb21fcG9pbnQoYWVzKGNvbD1wcm9iMiksIHNoYXBlPTIxLCBhbHBoYT0uNykgKwogIGdlb21fcG9pbnQoZGF0YT1hZ2dfZGYsIGFlcyh4PW1lYW5fcHJvYjEsIHk9bWVhbl91bmNlcnRhaW50eSwgc2hhcGU9YXMubG9naWNhbChjb3JyZWN0KSksIHNpemU9Mi41KSArCiAgI2dlb21fcG9pbnQoZGF0YT1hZ2dfZGYsIGFlcyh5PXVuY2VydGFpbnR5LCB4PW1lYW5fcHJvYjEsIHNoYXBlPWFzLmxvZ2ljYWwoY29ycmVjdCkpLCBzaXplPTIpICsKICBnZ3RpdGxlKCJVbmNlcnRhaW50eSB2cy4gc29mdG1heCBvdXRwdXQgb2YgcHJlZGljdGlvbiBmb3IgYWxsIG9ic2VydmF0aW9ucyIpICsKICBsYWJzKHg9InNvZnRtYXggb3V0cHV0IG9mIHByZWRpY3RlZCBjbGFzcyIsIHNoYXBlPSJjb3JyZWN0IikgKwogIHNjYWxlX2NvbG9yX2Rpc3RpbGxlcihuYW1lPSJSdW5uZXIgdXAiLAogICAgICAgICAgICAgICAgICAgICAgICBwYWxldHRlID0gIlNwZWN0cmFsIikgKwogIHNjYWxlX3NoYXBlX2Rpc2NyZXRlKG5hbWU9ZXhwcmVzc2lvbihwYXN0ZSgiKCIsYmFyKG11KVsicHJlZCJdLCIsICIsYmFyKHNpZ21hKVsicHJlZCJdLCIpIikpLAogICAgICAgICAgICAgICAgICAgICAgIGxhYmVscz1jKCJJbmNvcnJlY3QiLCAiQ29ycmVjdCIpKSArCiAgdGhlbWVfYncoKQpwNwpgYGAKCkEgYmx1ZSBwb2ludCBjb3JyZXNwb25kcyB0byBhbiBvYnNlcnZhdGlvbiB3aXRoIGEgbG93IHZhbHVlIG9mIGBwcm9iMmAsIHdoZXJlYXMgYSByZWQgcG9pbnQgY29ycmVzcG9uZHMgdG8gYW4gb2JzZXJ2YXRpb24gd2l0aCBhIGhpZ2ggdmFsdWUgb2YgYHByb2IyYC4gQWRkaXRpb25hbGx5LCB3ZSBoYXZlIHBsb3R0ZWQgdGhlIGF2ZXJhZ2UgbWVhbiBhbmQgdW5jZXJ0YWludHkgZm9yIGNvcnJlY3RseSAoYmxhY2sgZG90KSBhbmQgaW5jb3JyZWN0bHkgKGJsYWNrIHRyaWFuZ2xlKSBjbGFzc2lmaWVkIG9ic2VydmF0aW9ucy4KCkNsZWFybHksIHRoZSBsYXJnZXN0IHZhbHVlcyBvZiB0aGUgYHByb2IyYCBjbHVzdGVyIGFyb3VuZCBgcHJvYjFgLiBUaGlzIGlzIHRvIGJlIGV4cGVjdGVkLCBzaW1wbHkgYmVjYXVzZSB3aGVuIGBwcm9iMWAgJD0gMC41JCB3ZSBoYXZlIGEgbWF4aW11bSBvZiAibGVmdC1vdmVyIiBwcm9iYWJpbGl0eSBhdmFpbGFibGUgZm9yIGRpc3RyaWJ1dGlvbiBhbW9uZyB0aGUgb3RoZXIgY2xhc3NlcyBpbiAkXGhhdHtcbXV9JC4gSW4gb3RoZXIgd29yZHMsIHRoZSB2YWx1ZSBvZiBgcHJvYjJgIGlzIGNvbnN0cmFpbmVkIGJ5IGBwcm9iMWAuIEhvd2V2ZXIsIHRoZSBtYXhpbXVtIHZhbHVlcyBvZiAkXGhhdHtcc2lnbWF9X2skIGFwcGVhciB0byBiZSBhc3NvY2lhdGVkIHdpdGggcmVsYXRpdmVseSBsYXJnZSBwYWlycyBvZiBgcHJvYjFgIGFuZCBgcHJvYjJgLiBUaGlzIGNvdWxkIHN1Z2dlc3QgdGhhdCB1bmNlcnRhaW50eSBlc3RpbWF0aW9uIGJ5IGFkIGhvYyBtZXRob2RzIHN1Y2ggYXMgJFxoYXR7XHNpZ21hfV9rJCBjb3VsZCBiZSBtb3N0IHVzZWZ1bCBpbiBiaW5hcnkgY2xhc3NpZmljYXRpb24gc2V0dGluZ3MsIG9yIHRvIGRldGVjdCBzaXR1YXRpb25zIHdpdGggYSBzbWFsbCBudW1iZXIgb2YgY29tcGV0aW5nIGNsYXNzZXMgaW4gYSBtdWx0aWxhYmVsIHNldHRpbmcuCgpUaGUgb2JzZXJ2YXRpb25zIGNhbiBiZSBwYXJ0aXRpb25lZCBieSBjbGFzc2lmaWNhdGlvbiBzdGF0dXMgYW5kIG92ZXJsYXllZCB3aXRoIGEgMkQga2VybmVsIGRlbnNpdHkgZXN0aW1hdGUgKEtERSkuIFRoZSBLREUgZ2l2ZXMgYW4gaWRlYSBvZiB0aGUgam9pbnQgZGlzdHJpYnV0aW9uIG9mIGBwcm9iMWAgYW5kIGBwcm9iMmA6CgpgYGB7ciBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9NX0KIyBQbG90dGluZyB1bmNlcnRhaW50eSB2cy4gc29mdG1heCBvdXRwdXQgb2YgcHJlZGljdGlvbgpwOCA8LSBkZiAlPiUgCiAgZ2dwbG90KGFlcyh4PXByb2IxLCB5PXVuY2VydGFpbnR5KSkgKwogIGdlb21fcG9pbnQoYWVzKGNvbD1wcm9iMiksYWxwaGE9MC41KSArCiAgZ2VvbV9kZW5zaXR5XzJkKGNvbD0iYmxhY2siLCBhbHBoYT0uMykgKwogIGdndGl0bGUoIlVuY2VydGFpbnR5IHZzLiBzb2Z0bWF4IG91dHB1dCBvZiBwcmVkaWN0aW9uIGJ5IGluY29ycmVjdC9jb3JyZWN0IikgKwogIGxhYnMoeD0ic29mdG1heCBvdXRwdXQgb2YgcHJlZGljdGlvbiIpICsKICBmYWNldF9ncmlkKC5+YXMuZmFjdG9yKGNvcnJlY3QpKSArCiAgc2NhbGVfY29sb3JfZGlzdGlsbGVyKG5hbWU9IlJ1bm5lciB1cCIsCiAgICAgICAgICAgICAgICAgICAgICAgIHBhbGV0dGUgPSAiU3BlY3RyYWwiKSArCiAgdGhlbWVfYncoKQpwOApgYGAKClRoZSBibGFjayBjb250b3VyIGxpbmVzIGluZGljYXRlIHdoZXJlIG1vc3Qgb2YgdGhlIHBvaW50cyBhcmUgY29uY2VudHJhdGVkLiBUaGUgcGxvdCBvbiB0aGUgbGVmdCBpcyBmb3IgaW5jb3JyZWN0IHByZWRpY3Rpb25zLiBUaGUgcmlnaHQgaGFuZCBwbG90IHJlcHJlc2VudHMgdGhlIGNvcnJlY3QgcHJlZGljdGlvbnMuIEZvciB0aGUgY29ycmVjdCBwcmVkaWN0aW9ucywgaXQgc2VlbXMgYXMgaWYgZmFyIG1vcmUgb2YgdGhlIHBvaW50cyBhcmUgY29uY2VudHJhdGVkIGFyb3VuZCBoaWdoIHByZWRpY3RlZCBvdXRwdXQvbG93IHJ1bm5lci11cCBvdXRwdXQvbG93IHVuY2VydGFpbnR5LiBGb3IgdGhlIGluY29ycmVjdCBjbGFzc2lmaWNhdGlvbnMsIG1vc3Qgb2YgdGhlIHBvaW50cyBhcmUgY29uY2VudHJhdGVkIGFyb3VuZCB0aGUgYXJlYSB3aGVyZSAkXGhhdHtcc2lnbWF9X2skIHBlYWtzLiBUaGlzIGluZGljYXRlcyB0aGF0IHRoZSBhcHByb3hpbWF0ZWQgdW5jZXJ0YWludHkgZXN0aW1hdGVzIGluZGVlZCBjb250YWluIHZhbHVhYmxlIGluZm9ybWF0aW9uIGluIHRoZSBpbmNvcnJlY3QgY2FzZXMuCgojIyMgUnVubmVyLXVwIHByZWRpY3Rpb25zCgpUaGUgZm9sbG93aW5nIHBsb3Qgc2hvd3MgdGhlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIHVuY2VydGFpbnR5IGVzdGltYXRlcyBhbmQgdGhlIHNvZnRtYXggb3V0cHV0IG9mIHRoZSBydW5uZXItdXAgcHJlZGljdGlvbi4gVW5zdXJwcmlzaW5nbHksIG1vZGVsIHVuY2VydGFpbnR5IGluY3JlYXNlcyBhcyB0aGUgc29mdG1heCBvdXRwdXQgb2YgdGhlIHJ1bm5lci11cCBpbmNyZWFzZXMuIFdlIGhhdmUgcGxvdHRlZCBhIHNtb290aGVkIGVzdGltYXRlIG9mIHRoZSBtZWFuIHVuY2VydGFpbnR5IGFzIGEgZnVuY3Rpb24gb2YgdGhlIHJ1bm5lci11cCBvdXRwdXQgdG8gbWFrZSB0aGlzIGNsZWFyZXI6CgpgYGB7cn0KIyBQbG90dGluZyBzb2Z0bWF4IG91dHB1dCBvZiBydW5uZXItdXAgYWdhaW5zdCBlc3RpbWF0ZWQgdW5jZXJ0YWludHkKcDEwIDwtIGRmICU+JSAKICBnZ3Bsb3QoYWVzKHg9cHJvYjIsIHk9dW5jZXJ0YWludHkpKSArCiAgZ2VvbV9wb2ludChhbHBoYT0uMikgKwogIGdlb21fc21vb3RoKG1ldGhvZD0ibG9lc3MiKSArCiAgbGFicyh4PSJzb2Z0bWF4IG91dHB1dCBvZiBydW5uZXItdXAiKSArCiAgZ2d0aXRsZSgiVW5jZXJ0YWludHkgdnMuIHNvZnRtYXggb3V0cHV0IG9mIHJ1bm5lci11cCIpICsKICB0aGVtZV9idygpCnAxMApgYGAKCiMjIFVuY2VydGFpbnR5LXByZWRpY3Rpb24gY29ycmVsYXRpb24KCkFzIG1lbnRpb25lZCBpbiBzZWN0aW9uIDIuMiwgdGhlIGNvbm5lY3Rpb24gZXN0YWJsaXNoZWQgYmV0d2VlbiBkcm9wb3V0IG5ldXJhbCBuZXR3b3JrcyBhbmQgR1BzIGFyZSBsb3N0IHdoZW4gYXBwbGllZCB0byBjb252b2x1dGlvbmFsIG5ldXJhbCBuZXR3b3Jrcy4gUGVyZm9ybWluZyBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gZ2l2ZXMgdXMgYSBzaW1wbGUgd2F5IG9mIHRlc3RpbmcgaWYgdGhlIGFwcHJveGltYXRlZCB1bmNlcnRhaW50eSBpcyBhIHNpZ25pZmljYW50IHByZWRpY3RvciBvZiB0aGUgbW9kZWwncyBhYmlsaXR5IHRvIHByZWRpY3QgY29ycmVjdGx5OgoKYGBge3J9CiMgRml0dGluZyBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsIHRvIGNoZWNrIHNpZ25pZmljYW5jZSBvZiB1bmNlcnRhaW50eQptb2RlbF9zZCA8LSBnbG0oYXMuZmFjdG9yKGNvcnJlY3QpfnVuY2VydGFpbnR5LCBkYXRhPWRmLCBmYW1pbHkgPSBiaW5vbWlhbChsaW5rPSJsb2dpdCIpKQpzdW1tYXJ5KG1vZGVsX3NkKQpgYGAKClRoZSBjb2VmZmljaWVudCBhc3NvY2lhdGVkIHdpdGggYHVuY2VydGFpbnR5YCBpcyBoaWdobHkgc2lnbmlmaWNhbnQsIGluZGljYXRpbmcgdGhhdCB0aGUgZXN0aW1hdGVzIGxldmVyYWdlZCBmcm9tIE1DIGRyb3BvdXQgbWF5IGluZGVlZCBiZSBhIHVzZWZ1bCBxdWFudGlmaWNhdGlvbiBvZiBwcmVkaWN0aXZlIHVuY2VydGFpbnR5LgoKIyBSZWZlcnJhbCBDcml0ZXJpYQoKVGhlIHF1ZXN0aW9uIGlzIHRoZW46IEhvdyBkbyB3ZSBkZXRlcm1pbmUgYSByZWFzb25hYmxlIHVuY2VydGFpbnR5IHZhbHVlIGZvciByZWZlcnJhbCB0byBhIGh1bWFuIGV4cGVydD8gQXMgd2Ugc2F3IGluIHNlY3Rpb24gMy4xLjIsIHRoZSBtZWFuIHVuY2VydGFpbnR5IHZhbHVlcyBvZiB0aGUgaW5jb3JyZWN0IHByZWRpY3Rpb25zIGhpZ2hlciB0aGFuIGZvciB0aGUgY29ycmVjdCBwcmVkaWN0aW9ucyAoYHIgYWdnX2RmJG1lYW5fdW5jZXJ0YWludHlbMV1gIHZzLiBgciBhZ2dfZGYkbWVhbl91bmNlcnRhaW50eVsyXWAsIHJlc3BlY3RpdmVseSkuCgpOYWl2ZWx5LCB3ZSBjb3VsZCBzZXQgdGhlIHRocmVzaG9sZCBmb3IgcmVmZXJyYWwgdG8gdGhlIG1lYW4gdW5jZXJ0YWludHkgb2YgdGhlIGluY29ycmVjdGx5IGNsYXNzaWZpZWQgaW1hZ2VzOgoKYGBge3J9CiMgQ291bnRpbmcgbnVtYmVyIG9mIGNvcnJlY3QvaW5jb3JyZWN0IGJ5IHVuY2VydGFpbnR5ID49IC4xOCAKbWVhbl91bmMgPC0gZGYgJT4lIAogIGZpbHRlcihjb3JyZWN0PT0wKSAlPiUgCiAgc3VtbWFyaXNlKG1lYW5fdW5jPW1lYW4odW5jZXJ0YWludHkpKQoKcmVmZXJyYWwgPC0gZGYgJT4lIAogIGZpbHRlcih1bmNlcnRhaW50eT49bWVhbl91bmNbMSwxXSkgJT4lIAogIGNvdW50KGNvcnJlY3QpCnJlZmVycmFsCmBgYAoKVGhlIHByb2JsZW0gaGVyZSBpcyBhcHBhcmVudDogTWFueSBvZiB0aGUgY29ycmVjdGx5IGNsYXNzaWZpZWQgaW1hZ2VzIGFyZSBhc3NvY2lhdGVkIHdpdGggYSByZWxhdGl2ZWx5IGhpZ2ggbGV2ZWwgb2YgdW5jZXJ0YWludHkgKGluIG91ciBjYXNlLCB0aGlzIGlzIGR1ZSB0byB0aGUgYmltb2RhbGl0eSBvZiB0aGUgdW5jZXJ0YWludHkgZGlzdHJpYnV0aW9uIGluIHNlY3Rpb24gMy4yLjEpLiBXZSBzcGVjdWxhdGUgdGhhdCBhbHRob3VnaCB1bmNlcnRhaW50eSBzZWVtcyB0byBjb250YWluIHZhbHVlYWJsZSBpbmZvcm1hdGlvbiwgdGhlIHJlbGF0aXZlIHVuY2VydGFpbnRpZXMgb2YgdGhlIGNvcnJlY3QvaW5jb3JyZWN0IG9ic2VydmF0aW9ucyAoaW4gdGhpcyBjYXNlKSBtYXkgYmUgdG9vIHNtYWxsIHRvIGRpZmZlcmVudGlhdGUgd2hpY2ggaW1hZ2VzIHNob3VsZCBiZSByZWZlcnJlZCB0byBhbiBleHBlcnQuIFdlIG1heSBuZWVkIHRvIGFtcGxpZnkgdGhlIHF1YW50aWZpY2F0aW9uIG9mIHVuY2VydGFpbnR5IGluIHNvbWUgd2F5LgoKIyMgVXNlZnVsbmVzcyBvZiBydW5uZXItdXAgcHJlZGljdGlvbnMKCkZvciB0aGUgbW9zdCB1bmNlcnRhaW4gaW5jb3JyZWN0bHkgY2xhc3NpZmllZCBpbWFnZXMgdGhlIHJ1bm5lci11cCBzdWdnZXN0aW9ucyBhcmUgbm9uLXNlbnNpY2FsLiBTdGlsbCwgaXMgdGhlcmUgYW55IGluZm9ybWF0aW9uIHRvIGJlIG9idGFpbmVkIGZyb20gdGhlIHJ1bm5lci11cCBwcmVkaWN0aW9ucz8gV2hhdCB3b3VsZCBoYXBwZW4gdG8gb3VyIG92ZXJhbGwgYWNjdXJhY3kgaWYgd2UgdXNlZCB0aGUgcnVubmVyLXVwIHByZWRpY3Rpb25zIGZvciBhbGwgaW5jb3JyZWN0IGNsYXNzaWZpY2F0aW9ucz8KCmBgYHtyfQojIENvdW50aW5nIGNsYXNzaWZpY2F0aW9uIGFjY3VyYWN5IGlmIHJ1bm5lci11cCBpcyBlcXVhbCB0byBncm91bmQgdHJ1dGgKY2xhc3MyX2RmIDwtIGRmICU+JQogIG11dGF0ZShjb3JyZWN0PXJlcGxhY2UoY29ycmVjdCwgY29ycmVjdD09MCAmIGNsYXNzMj09dHJ1dGgsIDEpKSAlPiUgCiAgY291bnQoY29ycmVjdCkKY2xhc3MyX2RmCmBgYAoKQWNjdXJhY3kgd291bGQgcmlzZSB0byBgciBjbGFzczJfZGYkblsyXS8oc3VtKGNsYXNzMl9kZiRuKSlgLiBUaGlzIGluZGljYXRlcyB0aGF0IHRoZXJlIG1heSBiZSBzb21lIHZhbHVhYmxlIGluZm9ybWF0aW9uIHRvIGJlIGdhdGhlcmVkIGZyb20gdGhlIHJ1bm5lci11cCBwcmVkaWN0aW9ucy4gCgpgYGB7cn0KcnVubmVydXBfZGYgPC0gZGYgJT4lIAogIGZpbHRlcihjb3JyZWN0PT0wKSAlPiUgCiAgbXV0YXRlKHJ1bm5lcnVwID0gaWZlbHNlKGNsYXNzMj09dHJ1dGgsIDEsIDApKQoKbWVhbl9ydW5uZXJ1cCA8LSBydW5uZXJ1cF9kZiAlPiUKICBncm91cF9ieShydW5uZXJ1cCkgJT4lIAogIHN1bW1hcmlzZShtZWFudW5jZXJ0YWludHkgPSBtZWFuKHVuY2VydGFpbnR5KSwKICAgICAgICAgICAgbWVhbnByb2IxID0gbWVhbihwcm9iMSksCiAgICAgICAgICAgIG1lYW5wcm9iMiA9IG1lYW4ocHJvYjIpLAogICAgICAgICAgICBuPW4oKSkKYGBgCgpgYGB7cn0KcDExIDwtIHJ1bm5lcnVwX2RmICU+JSAKICBnZ3Bsb3QoYWVzKHg9dW5jZXJ0YWludHksIGdyb3VwPWZhY3RvcihydW5uZXJ1cCkpKSArCiAgZ2VvbV9oaXN0b2dyYW0oYWVzKHk9Li5kZW5zaXR5Li4sIGZpbGw9ZmFjdG9yKHJ1bm5lcnVwKSksIHBvc2l0aW9uPSJpZGVudGl0eSIsIGJpbnMgPSA1MCwgYWxwaGE9LjUpICsKICBnZW9tX2RlbnNpdHkoYWVzKHk9Li5kZW5zaXR5Li4sIGNvbD1mYWN0b3IocnVubmVydXApKSwgYWxwaGE9LjUpICsKICBnZW9tX3J1ZyhhZXMoeD11bmNlcnRhaW50eSwgY29sPWZhY3RvcihydW5uZXJ1cCkpLCBhbHBoYT0uNSkgKwogIGdlb21fdmxpbmUoZGF0YSA9IG1lYW5fcnVubmVydXAsIGFlcyh4aW50ZXJjZXB0PW1lYW51bmNlcnRhaW50eSwgY29sPWZhY3RvcihydW5uZXJ1cCkpLCBsdHk9ImRhc2hlZCIpICsKICBnZ3RpdGxlKCJEaXN0cmlidXRpb25zIG9mIHVuY2VydGFpbnR5IikgKwogIGxhYnMoY29sb3I9IlByZWRpY3Rpb24iLAogICAgICAgZmlsbD0iUHJlZGljdGlvbiIpICsKICBzY2FsZV9jb2xvcl9kaXNjcmV0ZShicmVha3M9YygiMCIsICIxIiksCiAgICAgICAgICAgICAgICAgICAgICAgICBsYWJlbHM9YygiMDogSW5jb3JyZWN0IiwgIjE6IENvcnJlY3QiKSkgKwogIHNjYWxlX2ZpbGxfZGlzY3JldGUoYnJlYWtzPWMoIjAiLCAiMSIpLAogICAgICAgICAgICAgICAgICAgICAgICAgbGFiZWxzPWMoIjA6IEluY29ycmVjdCIsICIxOiBDb3JyZWN0IikpICsKICB0aGVtZV9idygpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSBjKC45LC44NSkpCnAxMQpgYGAKCmBgYHtyfQpwMTIgPC0gcnVubmVydXBfZGYgJT4lIAogIGdncGxvdChhZXMoeD1wcm9iMSwgZ3JvdXA9ZmFjdG9yKHJ1bm5lcnVwKSkpICsKICBnZW9tX2RlbnNpdHkoYWVzKHk9Li5kZW5zaXR5Li4sIGNvbD1mYWN0b3IocnVubmVydXApKSwgYWxwaGE9LjUpICsKICBnZW9tX3J1ZyhhZXMoeD1wcm9iMSwgY29sPWZhY3RvcihydW5uZXJ1cCkpLCBhbHBoYT0uNSkgKwogIGdlb21fdmxpbmUoZGF0YSA9IG1lYW5fcnVubmVydXAsIGFlcyh4aW50ZXJjZXB0PW1lYW5wcm9iMSwgY29sPWZhY3RvcihydW5uZXJ1cCkpLCBsdHk9ImRhc2hlZCIpICsKICBnZ3RpdGxlKCJEaXN0cmlidXRpb25zIG9mIHNvZnRtYXggcHJlZGljdGlvbnMiKSArCiAgbGFicyhjb2xvcj0iUHJlZGljdGlvbiIsCiAgICAgICBmaWxsPSJQcmVkaWN0aW9uIikgKwogIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKGJyZWFrcz1jKCIwIiwgIjEiKSwKICAgICAgICAgICAgICAgICAgICAgICAgIGxhYmVscz1jKCIwOiBJbmNvcnJlY3QiLCAiMTogQ29ycmVjdCIpKSArCiAgc2NhbGVfZmlsbF9kaXNjcmV0ZShicmVha3M9YygiMCIsICIxIiksCiAgICAgICAgICAgICAgICAgICAgICAgICBsYWJlbHM9YygiMDogSW5jb3JyZWN0IiwgIjE6IENvcnJlY3QiKSkgKwogIHRoZW1lX2J3KCkgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9IGMoLjksLjg1KSkKcDEyCmBgYAoKCmBgYHtyfQpwMTMgPC0gcnVubmVydXBfZGYgJT4lIAogIGdncGxvdChhZXMoeD1wcm9iMiwgZ3JvdXA9ZmFjdG9yKHJ1bm5lcnVwKSkpICsKICBnZW9tX2RlbnNpdHkoYWVzKHk9Li5kZW5zaXR5Li4sIGNvbD1mYWN0b3IocnVubmVydXApKSwgYWxwaGE9LjUpICsKICBnZW9tX3J1ZyhhZXMoeD1wcm9iMiwgY29sPWZhY3RvcihydW5uZXJ1cCkpLCBhbHBoYT0uNSkgKwogIGdlb21fdmxpbmUoZGF0YSA9IG1lYW5fcnVubmVydXAsIGFlcyh4aW50ZXJjZXB0PW1lYW5wcm9iMiwgY29sPWZhY3RvcihydW5uZXJ1cCkpLCBsdHk9ImRhc2hlZCIpICsKICBnZ3RpdGxlKCJEaXN0cmlidXRpb25zIG9mIHJ1bm5lciB1cCBzb2Z0bWF4IHByb2JhYmlsaXRpZXMiKSArCiAgbGFicyhjb2xvcj0iUHJlZGljdGlvbiIsCiAgICAgICBmaWxsPSJQcmVkaWN0aW9uIikgKwogIHNjYWxlX2NvbG9yX2Rpc2NyZXRlKGJyZWFrcz1jKCIwIiwgIjEiKSwKICAgICAgICAgICAgICAgICAgICAgICAgIGxhYmVscz1jKCIwOiBJbmNvcnJlY3QiLCAiMTogQ29ycmVjdCIpKSArCiAgc2NhbGVfZmlsbF9kaXNjcmV0ZShicmVha3M9YygiMCIsICIxIiksCiAgICAgICAgICAgICAgICAgICAgICAgICBsYWJlbHM9YygiMDogSW5jb3JyZWN0IiwgIjE6IENvcnJlY3QiKSkgKwogIHRoZW1lX2J3KCkgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9IGMoLjksLjg1KSkKcDEzCmBgYAoKU28gaG93IGRvIHdlIGRldGVybWluZSB3aGljaCBpbWFnZXMgdG8gdGFrZSBhIGNsb3NlciBsb29rIGF0PwoKIyMgTGV2ZXJhZ2luZyBSdW5uZXItdXAgUHJvYmFiaWxpdGllcwoKT25lIHBvc3NpYmxlIGFwcHJvYWNoIGlzIHRvIGluY29ycG9yYXRlIGluZm9ybWF0aW9uIGZyb20gdGhlIHZhbHVlIG9mICRcdGF1X3tqa30kLCB3aGljaCB3ZSBpbnRyb2R1Y2VkIGluIHNlY3Rpb24gMi41LiBDb25zaWRlciB0aGUgZm9sbG93aW5nIGNhc2VzOgoKKiAkXHRhdV97a2p9IFxhcHByb3ggMSQgbWVhbnMgdGhhdCBgZGlmZmAgYW5kIGB1bmNlcnRhaW50eWAgYXJlIHJlbGF0aXZlbHkgc2ltaWxhci4gVGhpcyBoYXBwZW5zIGlmIGEpIHRoZSBtb2RlbHMgaGF2ZSBmYWlsZWQgdG8gYWdyZWUgb24gYSBjbGVhciBmYXZvdXJpdGUgKGBkaWZmYCBpcyBzbWFsbCkgYnV0IG1vZGVsIHVuY2VydGFpbnR5IGlzIGxvdywgb3IgYikgdGhlIG1vZGVscyBoYXZlIGEgZmF2b3VyaXRlIChgZGlmZmAgaXMgbGFyZ2UpIGJ1dCBtb2RlbCB1bmNlcnRhaW50eSBpcyBoaWdoLiBMZXQncyBjYWxsIHRoZXNlICoqcmVmZXJyYWwgcHJlZGljdGlvbnMqKi4KCiogJFx0YXVfe2tqfSBcdG8gMCQgbWVhbnMgdGhhdCBgdW5jZXJ0YWludHlgIGlzIG11Y2ggbGFyZ2VyIHRoYW4gYGRpZmZgLiBUaGVzZSBzaG91bGQgcmVwcmVzZW50ICoqdW5jZXJ0YWluIHByZWRpY3Rpb25zKiouCgoqICRcdGF1X3tran0gXHRvIFxpbmZ0eSQgbWVhbnMgdGhhdCBgdW5jZXJ0YWludHlgIGlzIG11Y2ggc21hbGxlciB0aGFuIGBkaWZmYC4gVGhlc2Ugc2hvdWxkIHJlcHJlc2VudCAqKm5vbi1yZWZlcnJhbCBwcmVkaWN0aW9ucyoqLgoKQXMgd2Ugc2F3IGluIHNlY3Rpb24gMywgdGhlIG1lYW4gJFx0YXVfe2prfSQgKGdpdmVuIGJ5IGBtZWFuX3JhdGlvYCkgZm9yIHRoZSBpbmNvcnJlY3RseSBjbGFzc2lmaWVkIGltYWdlcyBpcyBgciBhZ2dfZGYkbWVhbl9yYXRpb1sxXWAgYW5kIGByIGFnZ19kZiRtZWFuX3JhdGlvWzJdYCBmb3IgdGhlIGNvcnJlY3RseSBjbGFzc2lmaWVkIGltYWdlcy4gU2V0dGluZyB0aGUgcmVmZXJyYWwgdGhyZXNob2xkIHRvIHRoZSBtZWFuICRcdGF1X3tqa30kIGZvciB0aGUgaW5jb3JyZWN0IGNsYXNzaWZpY2F0aW9ucyAoYHIgYWdnX2RmJG1lYW5fcmF0aW9bMV1gKSwgd2UgZ2V0OgoKYGBge3J9CiMgQ291bnRpbmcgbnVtYmVyIG9mIGNvcnJlY3QvaW5jb3JyZWN0IGJ5IHRhdSA8PSAyLjgKbWVhbl90YXUgPC0gZGYgJT4lIAogIGZpbHRlcihjb3JyZWN0PT0wKSAlPiUgCiAgc3VtbWFyaXNlKG1lYW5fdGF1PW1lYW4oZGlmZl9zZF9yYXRpbykpCiAgCnJlZmVycmFsX21lYW4gPC0gZGYgJT4lIAogIGZpbHRlcihkaWZmX3NkX3JhdGlvIDw9IG1lYW5fdGF1WzEsMV0pICU+JSAKICBjb3VudChjb3JyZWN0KQpyZWZlcnJhbF9tZWFuCmBgYAoKV2UgcnVuIGludG8gdGhlIHNhbWUgcHJvYmxlbSBhcyB3aGVuIHdlIHVzZWQgdGhlIG1lYW4gdW5jZXJ0YWludHk6IE1hbnkgb2YgdGhlIGNvcnJlY3RseSBwcmVkaWN0ZWQgaW1hZ2VzIHdvdWxkIGJlIHJlZmVycmVkLCBpbiBmYWN0IG1vcmUgdGhhbiB3aGVuIHdlIHVzZWQgdGhlIHVuY2VydGFpbnR5IGVzdGltYXRlcy4gSXQgaXMgaW50ZXJlc3RpbmcgdG8gbm90ZSwgaG93ZXZlciwgdGhhdCB3ZSBnZXQgZmFyIG1vcmUgcmVmZXJyYWxzIG9mIGluY29ycmVjdGx5IGNsYXNzaWZpZWQgaW1hZ2VzLiBBZ2FpbiwgdGhpcyBtYXkgaW5kaWNhdGUgdGhhdCAkXHRhdV97amt9JCBpcyBhIHVzZWZ1bCBtZWFzdXJlIG9mIHVuY2VydGFpbnR5LgoKU2V0dGluZyB0aGUgcmVmZXJyYWwgcmF0ZSBvZiB0aGUgbWVhbiAkXHRhdV97amt9IFxsZXEgMSQgZ2l2ZXMgdXMgdGhlIGZvbGxvd2luZzoKCmBgYHtyfQojIENvdW50aW5nIG51bWJlciBvZiBjb3JyZWN0L2luY29ycmVjdCBieSB0YXUgPD0gMQptZWRpYW5fdGF1IDwtIGRmICU+JSAKICBmaWx0ZXIoY29ycmVjdD09MCkgJT4lIAogIHN1bW1hcmlzZShtZWRpYW5fdGF1PW1lZGlhbihkaWZmX3NkX3JhdGlvKSkKCnJlZmVycmFsXzEgPC0gZGYgJT4lIAogIGZpbHRlcihkaWZmX3NkX3JhdGlvIDw9IDEpICU+JSAKICBjb3VudChjb3JyZWN0KQpyZWZlcnJhbF8xCmBgYAoKVGhpcyBpcyBhIGNsZWFyIGltcHJvdmVtZW50IG92ZXIgb3VyIGZpcnN0IGFwcHJvYWNoLCBpbiB0ZXJtcyBvZiB0aGUgYW1vdW50IG9mIHJlZmVycmVkIGltYWdlcy4gYHIgcmVmZXJyYWxfbWVhbiRuWzFdIC0gcmVmZXJyYWxfMSRuWzFdYCBmZXdlciBpbmNvcnJlY3QgaW1hZ2VzIGFyZSByZWZlcnJlZCBjb21wYXJlZCB0byBgciByZWZlcnJhbF9tZWFuJG5bMl0gLSByZWZlcnJhbF8xJG5bMl1gIGZld2VyIGNvcnJlY3QgaW1hZ2VzLiBUaGlzIGNvdWxkIGluZGljYXRlIHRoYXQgJFx0YXVfe2prfSQgaXMgYSB1c2VmdWwgcXVhbnRpZmljYXRpb24gb2YgdW5jZXJ0YWludHkuCgojIFJlZmVyZW5jZXMKClsxXSBHYWwsIFkuICYgR2hhaHJhbWFuaSwgWi4gKkJheWVzaWFuIENvbnZvbHV0aW9uYWwgTmV1cmFsIE5ldHdvcmtzIHdpdGggQmVybm91bGxpIEFwcHJveGltYXRlIFZhcmlhdGlvbmFsIEluZmVyZW5jZSouIGFyWGl2OiAxNTA2LjAyMTU4ICgyMDE1KS4KClsyXSBHYWwsIFkuICYgR2hhaHJhbWFuaSwgWi4gKkRyb3BvdXQgYXMgYSBCYXllc2lhbiBBcHByb3hpbWF0aW9uOiBSZXByZXNlbnRpbmcgTW9kZWwgVW5jZXJ0YWludHkgaW4gRGVlcCBMZWFybmluZyouIGFyWGl2OiAxNTA2LjAyMTQyICgyMDE1KS4KClszXSBHYWwsIFkuICYgR2hhaHJhbWFuaSwgWi4gKkRyb3BvdXQgYXMgYSBCYXllc2lhbiBBcHByb3hpbWF0aW9uOiBBcHBlbmRpeCouIGFyWGl2OiAxNTA2LjAyMTU3ICgyMDE1KS4KCls0XSBMZWliaWcsIEMuICYgQWxsa2VuLCBWLiBldC4gYWwuICpMZXZlcmFnaW5nIHVuY2VydGFpbnR5IGluZm9ybWF0aW9uIGZyb20gZGVlcCBuZXVyYWwgbmV0d29ya3MgZm9yIGRpc2Vhc2UgZGV0ZWN0aW9uKi4gU2NpZW50aWZpYyBSZXBvcnRzIHZvbHVtZSA3LCBBcnRpY2xlIG51bWJlcjogMTc4MTYgKDIwMTcpLgoKWzVdIEhpbnRvbiwgRy4gJiBTcml2YXN0YXZhLCBOLiBldC4gYWwuICpJbXByb3ZpbmcgbmV1cmFsIG5ldHdvcmtzIGJ5IHByZXZlbnRpbmcgY28tYWRhcHRhdGlvbiBvZiBmZWF0dXJlIGRldGVjdG9ycyouIGFyWGl2OiAxMjA3LjA1ODAgKDIwMTIpLgoKWzZdIExlaWJpZywgQy4gJiBBbGxrZW4sIFYuIGV0LiBhbC4gKkxldmVyYWdpbmcgdW5jZXJ0YWludHkgaW5mb3JtYXRpb24gZnJvbSBkZWVwIG5ldXJhbCBuZXR3b3JrcyBmb3IgZGlzZWFzZSBkZXRlY3Rpb246IHN1cHBsZW1lbnRhcnkgbWF0ZXJpYWwqLiBTY2llbnRpZmljIFJlcG9ydHMgdm9sdW1lIDcsIEFydGljbGUgbnVtYmVyOiAxNzgxNiAoMjAxNykuCgpbN10gU21pdGgsIEwuLCAmIEdhbCwgWS4gKipVbmRlcnN0YW5kaW5nIE1lYXN1cmVzIG9mIFVuY2VydGFpbnR5IGZvciBBZHZlcnNhcmlhbCBFeGFtcGxlIERldGVjdGlvbi4qKiBhclhpdiBwcmVwcmludCBhclhpdjoxODAzLjA4NTMzLiAoMjAxOCk=